组合数学问题
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define mod 20130303 typedef long long ll; using namespace std; char s[1010]; int d,len; //之前RE因为这里d,len都定义成char类型... int vis[10]; ll c[1010][1010]; void init(){ int i,j; for(i=0;i<=1000;i++) c[i][0]=1; for(i=1;i<=1000;i++) for(j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } ll count(){ int i,all=0; ll ans=1; for(i=0;i<10;i++) all+=vis[i]; for(i=0;i<10;i++){ ans=(ans*c[all][vis[i]])%mod; all-=vis[i]; } return ans; } ll solve(){ ll tem=0; int i; for(i=1;i<10;i++){ if(vis[i]){ vis[i]--; tem=(tem+count())%mod; vis[i]++; } } return tem; } ll dfs(int pos){ int i,j; ll tem=0; if(pos==len)return 0; if(pos==0)i=1; else i=0; for(j=i;j<s[pos]-'0';j++){ if(vis[j]){ vis[j]--; tem=(tem+count())%mod; vis[j]++; } } vis[j]--; tem=(tem+dfs(pos+1))%mod; return tem; } int main(){ int t,T,i; //freopen("a.txt","r",stdin); //freopen("b.txt","w",stdout); init(); scanf("%d",&T); for(t=1;t<=T;t++){ scanf("%s %d",s,&d); len=strlen(s); memset(vis,0,sizeof(vis)); for(i=0;i<len;i++) vis[s[i]-'0']++; int tem=vis[d]; ll sum=0; for(i=0;i<tem;i++){ vis[d]=i; sum=(sum+solve())%mod; } vis[d]=tem; sum=(sum+dfs(0))%mod; cout<<sum<<endl; } return 0; }