洛谷P2518 [HAOI2010]计数

题目描述

你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。

现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.

输入输出格式

输入格式：

只有1行，为1个整数n.

输出格式：

只有整数，表示N之前出现的数的个数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

n的长度不超过50，答案不超过2^63-1.

题解

　　挺裸的数位dp（虽然我并不会）

　　懒得写了，直接贴一下->这里

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 #define ll long long
 5 using namespace std;
 6 const int N=1005;
 7 int a[N],v[N],n;ll c[N][N],ans;
 8 ll gc(int n,int m){
 9     if(c[n][m]) return c[n][m];
10     if(m==1) return n;
11     if(m==0||m==n) return 1;
12     if(m>n) return 0;
13     c[n][m]=gc(n-1,m)+gc(n-1,m-1);
14     return c[n][m];
15 }
16 ll calc(){
17     ll res=1;
18     int m=n;
19     for(int i=0;i<10;++i) if(a[i]) res*=gc(m,a[i]),m-=a[i];
20     return res;
21 }
22 int main(){
23     //freopen("testdata.in","r",stdin);
24     char ch;
25     while(cin>>ch)if(isdigit(ch))v[++n]=ch-48,a[v[n]]++;
26     int nn=n;
27     for(int i=1;i<=nn;++i){
28         --n;
29         for(int j=0;j<v[i];++j)
30         if(a[j]){--a[j],ans+=calc(),++a[j];}
31         --a[v[i]];
32     }
33     printf("%lld
",ans);
34     return 0;
35 }