[ZOJ 3662] Math Magic (动态规划+状态压缩)

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <map>
 6 #include <iterator>
 7 #include <vector>
 8 using namespace std;
 9 typedef long long LL;
10 
11 int n,m,k;
12 int p[1000],h[1000],w[1000],v[1000],ptr;
13 int dp[111][1100][1<<5];
14 const int MOD = 1000000007;
15 
16 void prime_factor(int x){
17     for(int i=2;i*i<=x;i++){
18         while( x%i==0 ){
19             p[i]++;
20             x /= i;
21         }
22     }
23     if( x!=1 ) p[x] = 1;
24 }
25 
26 void handle(int x){
27     w[++ptr] = x;
28     for(int i=2;i*i<=x;i++){
29         int t = 0;
30         while( x%i==0 ){
31             t ++;
32             x /= i;
33         }
34         if( t&&t==p[i] ) v[ptr] |= (1<<(h[i]-1));
35     }
36     if( x!=1&&p[x]==1 ) v[ptr] |= (1<<(h[x]-1));
37 }
38 
39 int main(){
40     while(scanf("%d%d%d",&n,&m,&k)!=EOF){
41         ptr = 0;
42         memset(p,0,sizeof(p));
43         memset(w,0,sizeof(w));
44         memset(v,0,sizeof(v));
45         memset(h,0,sizeof(h));
46         prime_factor(m);
47         int sn = 0;
48         for(int i=0;i<1000;i++){
49             if( p[i] ) {
50                 h[i] = ++sn;
51             }
52         }
53         for(int i=2;i*i<=m;i++){
54             if( m%i==0 ) {
55                 handle(i);
56                 if( i*i!=m ) handle(m/i);
57             }
58         }
59         handle(1);
60         if(m!=1) handle(m);
61         memset(dp,0,sizeof(dp));
62         dp[0][0][0] = 1;
63         for(int j=1;j<=k;j++){
64             for(int i=1;i<=ptr;i++){
65                 for(int k=0;k<=n;k++){
66                     for(int mask=0;mask<(1<<sn);mask++){
67                         if( k+w[i]<=n&&(mask|v[i])<(1<<sn) ){
68                             dp[j][k+w[i]][mask|v[i]] = (dp[j][k+w[i]][mask|v[i]]+dp[j-1][k][mask])%MOD;
69                         }
70                     }
71                 }
72             }
73         }
74         printf("%d\n",dp[k][n][(1<<sn)-1]);
75     }
76     return 0;
77 }