题目描述
你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。
现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.
输入输出格式
输入格式：只有1行，为1个整数n.
输出格式：只有整数，表示N之前出现的数的个数。
输入输出样例
输入样例#1：
1020
输出样例#1：
7
说明
n的长度不超过50，答案不超过2^63-1.
Solution：
本题组合数学（感觉不像数位dp啊）。
题意就是给你一个50位的数，求用各数位上的数能组成多少小于它的数。
我们把给定的数当作n个数字的一个排列（不足n位的可以理解为含有前导0），那么题意转化为字典序小于当前排列的个数有多少个。
于是统计下各个数码的出现次数，然后就能一位一位的计算情况了。考虑到了第$i$位小于某一排列的情况，直接枚举第$i$位可填的数字，那么后面的$n-i$个数位可以随便填数，设剩下的数码个数依次为$a_0,a_1,a_2…a_9$，则填$0$有$C(n-i,a_0)$种方案，再填$1$有$C(n-i-a_0,a_1)$种方案…不难得到当前的总方案为$C(n-i,a_0)*C(n-i-a_0,a_1)…*C(n-i-a_0-a_1-…a_8,a_9)$。然后累加每位填数情况的方案数就好了。
代码：
/*Code by 520 -- 9.18*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) using namespace std; const int N=55; int n,a[N],cnt,tot[N]; char s[N]; ll ans,c[N][N]; il ll calc(){ ll ans=1; int m=cnt; For(i,0,9) if(tot[i]) ans*=c[m][tot[i]],m-=tot[i]; return ans; } int main(){ For(i,0,50) c[i][0]=1; For(i,1,50) For(j,1,i) c[i][j]=c[i-1][j]+c[i-1][j-1]; scanf("%s",s+1),n=cnt=strlen(s+1); For(i,1,cnt) a[i]=(s[i]^48),tot[a[i]]++; For(i,1,n) { cnt--; For(j,0,a[i]-1) if(tot[j]) tot[j]--,ans+=calc(),tot[j]++; tot[a[i]]--; } cout<<ans; return 0; }