[BZOJ1025][SCOI2009]游戏 DP+置换群

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1025

题目中的排数就是多少次回到原来的序列。很显然对于题目所描述的任意一种对应法则，其中一定有一个或者多个循环节。

设有$m$个循环节，每个循环节的大小为$A_i$，则回到最开始的序列需要置换$lcm{A_i} (i=1->m)$次。

于是问题变成了求$n=sum_{i=1}^mA_i$，且$lcm{A_i} (i=1->m)$各不相同的${A}$有多少种。

我们可以用一种很神的方法。首先可以发现对于任意一个数$A_i$，我们可以把它拆成若干个总和小于等于$A_i$的互不相同的质数，以及若干个1来提供对答案等价的贡献，证明显然。然后就很容易想到用枚举质数，直接把每一个$A_i$用一个质数$pri_i$的$s_i$次方来表示。这样其实就变成了类似于背包的问题，每一个$A_i$和1就是物品，背包容量就是$A_i$的总和，之后就很容易DP了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 int cnt=0,p[1010];
 7 bool vis[1010];
 8 void sieve(){
 9     for(int i=2;i<=1000;i++){
10         if(!vis[i]) p[++cnt]=i;
11         for(int j=1;j<=cnt&&i*p[j]<=1000;j++){
12             vis[i*p[j]]=true;
13             if(i%p[j]==0) break;
14         }
15     }
16 }
17 int n;
18 ll f[1010][1010];
19 void dp(){
20     ll ans=0;
21     f[0][0]=1;
22     for(int i=1;i<=cnt;i++){
23         for(int j=0;j<=n;j++) f[i][j]=f[i-1][j];
24         for(int j=p[i];j<=n;j*=p[i])
25             for(int k=0;k+j<=n;k++)
26                 f[i][k+j]+=f[i-1][k];
27     }
28     for(int i=0;i<=n;i++) ans+=f[cnt][i];
29     printf("%lld
",ans);
30 }
31 int main(){
32     scanf("%d",&n);
33     sieve();
34     dp();
35     return 0;
36 }