[SCOI2009]游戏

根据题意每个数经过k次变换终会回到自身；
置换的思想；
离散数学里的知识；
n个数可以分成m个集合，这m个集合元素的总数==n;
相当于在n个数中分别选取a,b,c...个数组成m个集合；
比如：假设8个数组成3个集合
可以为224 （即第一个集合元素2，第二个2，第三个4）
为了节省时间：
每个集合大小ai可以表达为若干个质因数的h次幂形式；
即从质数中选取k个按照一定的幂次，使其和等于h
dp[i][j]表示前i个质数，和为j的种类数
dp[i][j]+=dp[i-1][j-is_prime[i]^k];

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1010;
int dp[maxn],cnt=0,is_prime[maxn],prime[maxn];
void find(int n)
{
    prime[1]=1,prime[0]=1;
    for(int i=2;i<=n;i++)
    {
        if(prime[i]==1) continue;
        is_prime[cnt++]=i;//记录n以内的质因数
        for(int j=i+i;j<=n;j+=i)
        {
            prime[j]=1;
        }
    }
    return;
}
signed main()
{
    int n;
    scanf("%d",&n);
    memset(prime,0,sizeof(prime));
    memset(is_prime,0,sizeof(is_prime));
    find(n);
    dp[0]=1;//完全背包
    for(int i=0;i<cnt;i++)
    {
        for(int j=n;j>=is_prime[i];j--)
        {
            int l=is_prime[i];
            while(l<=j) dp[j]+=dp[j-l],l*=is_prime[i];
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        ans+=dp[i];
    }
    cout<<ans<<endl;
}