ZOJ3662Math Magic解题报告

状态压缩DP，先对M进行质因子分解，记录其次数，然后对M的所有因子进行统计，分别计算每个因子对应的状态（只有当因子的质因子次数和M相同时这一位才置1），也就是说，如果一个数的每一个质因子次数都没有达到M的质因子次数这个数所表示的状态就是0，然后进行状态DP，其实就是递推，不能算是DP，这个用递推会比记忆化搜索要好，因为记忆化搜索的时候要考虑到底要不要取某一个值，取多少个，用异或没有递推的时候用|实现简单

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define SUM 1005
 5 #define STATE 20
 6 #define N 105
 7 #define MOD 1000000007
 8 using namespace std;
 9 int dp[N][STATE][SUM];
10 bool isprime[SUM];
11 int prime[200],cnt;
12 int dn,res[4];
13 int g[STATE][100],num[STATE]; 
14 void init()
15 {
16     int i,j;
17     memset(isprime,true,sizeof(isprime));
18     cnt=0;
19     for(i=2;i<=1000;i++)
20     {
21         if(isprime[i])
22         {
23             prime[cnt++]=i;
24             for(j=i*i;j<=1000;j+=i)
25                 isprime[j]=false;
26         }
27     }
28 }
29 int main()
30 {
31     init();
32     int n,m,k,i,j,temp,tn,pn;
33     while(scanf("%d%d%d",&m,&n,&pn)!=EOF)
34     {
35         tn=n;
36         dn=0;
37         memset(dp,0,sizeof(dp));
38         for(i=0;i<cnt;i++)
39         {
40             if(n%prime[i]==0)
41             {
42                 temp=n;
43                 while(n%prime[i]==0)
44                 {
45                     n/=prime[i];
46                 }
47                 res[dn]=temp/n;//只需要记录每一个质因子对应的最大因子
48                 dn++;
49                 if(n==1)
50                     break;
51             }
52         }
53         int sta;
54         memset(num,0,sizeof(num));
55         for(i=1;i<=tn;i++)
56         {
57             if(tn%i==0)
58             {
59                 sta=0;
60                 for(j=0;j<dn;j++)
61                 {
62                     if(i%res[j]==0)
63                         sta|=(1<<j);
64                 }
65                 g[sta][num[sta]++]=i;
66             }
67         }
68         dp[0][0][0]=1;
69         for(i=0;i<pn;i++)
70             for(j=0;j<(1<<dn);j++)
71                 for(k=0;k<m;k++)
72                 {
73                     if(dp[i][j][k])
74                     {
75                         for(int l=0;l<(1<<dn);l++)
76                             for(int t=0;t<num[l];t++)
77                             {
78                                 if(i+1<=pn&&k+g[l][t]<=m)
79                                 {
80                                     dp[i+1][j|l][k+g[l][t]]+=dp[i][j][k];
81                                     dp[i+1][j|l][k+g[l][t]]%=MOD;
82                                 }
83                             }
84                     }
85                 }
86         printf("%d\n",dp[pn][(1<<dn)-1][m]);
87     }
88     return 0;
89 }