LightOJ1158 Anagram Division（状压DP）

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int d[1<<10][1111],fact[11]={1};
 5 int main(){
 6     for(int i=1; i<11; ++i) fact[i]=fact[i-1]*i;
 7     int t,m;
 8     char str[1111];
 9     scanf("%d",&t);
10     for(int cse=1; cse<=t; ++cse){
11         scanf("%s%d",str,&m);
12         int n=strlen(str);
13         memset(d,0,sizeof(d));
14         d[0][0]=1;
15         for(int i=0; i<(1<<n)-1; ++i){
16             for(int j=0; j<m; ++j){
17                 if(d[i][j]==0) continue;
18                 for(int k=0; k<n; ++k){
19                     if((i>>k)&1) continue;
20                     d[i|(1<<k)][(j*10+str[k]-‘0‘)%m]+=d[i][j];
21                 }
22             }
23         }
24         int times[10]={0};
25         for(int i=0; i<n; ++i) ++times[str[i]-‘0‘];
26         for(int i=0; i<10; ++i){
27             d[(1<<n)-1][0]/=fact[times[i]];
28         }
29         printf("Case %d: %d\n",cse,d[(1<<n)-1][0]);
30     }
31     return 0;
32 }