题目描述
你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。
现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.
输入输出格式
输入格式：
只有1行，为1个整数n.
输出格式：
只有整数，表示N之前出现的数的个数。
输入输出样例
说明
n的长度不超过50，答案不超过2^63-1.
题解
挺裸的数位dp（虽然我并不会）
懒得写了，直接贴一下->这里
//minamoto
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=;
int a[N],v[N],n;ll c[N][N],ans;
ll gc(int n,int m){
if(c[n][m]) return c[n][m];
if(m==) return n;
if(m==||m==n) return ;
if(m>n) return ;
c[n][m]=gc(n-,m)+gc(n-,m-);
return c[n][m];
}
ll calc(){
ll res=;
int m=n;
for(int i=;i<;++i) if(a[i]) res*=gc(m,a[i]),m-=a[i];
return res;
}
int main(){
//freopen("testdata.in","r",stdin);
char ch;
while(cin>>ch)if(isdigit(ch))v[++n]=ch-,a[v[n]]++;
int nn=n;
for(int i=;i<=nn;++i){
--n;
for(int j=;j<v[i];++j)
if(a[j]){--a[j],ans+=calc(),++a[j];}
--a[v[i]];
}
printf("%lld\n",ans);
return ;
}