分析

我们先引入一个概念，置换。这里我简单的说一下，就是把 个元素的其它排列与原排列的映射关系。 可以用一个数组表示 。而这个道题就是给出一个置换，求有多少个不同的循环。为什么置换存在循环。不难发现，如果把每个数字看作一个节点，那么每个节点都有一个后驱节点和一个前驱节点，所以出度和入度都为 ，那么这个图必然构成若干个环。如果每个循环的长度为 ，那么在 次变化之后，置换一定变回原样。既然这道题要求有多少个循环，其实就是求 可以分解为多少个数的 的种类数。因为 。所以我们只需要在转移时，保证转移时 这样，可以不用考虑 的影响。定义状态 为考虑前 个质数，最后 的值 。那么答案为 。因为最后你总可以用 把后面填满，要注意 是从 开始枚举的，因为还有全是 的方案。其实把置换拆成循环的题还是比较多的 比如这道题 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
#define LL long long
int read() {int x;scanf("%d",&x);return x;}
LL f[2][N],g[N],n,vis[N];
void work(int x) {
    g[++g[0]] = 1;
    for(int i = 2;i <= x;i++) {
        if(!vis[i]) g[++g[0]] = i;
        for(int j = 1;j <= g[0] && g[j] * i <= x;j++) {
            vis[g[j] * i] = 1;if(!(g[j] % i)) break;
        }
     }
}
int main() {
    n = read();
    work(n);f[0][0] = 1;
//    for(int i = 1;i <= g[0];i++) cout << g[i] << endl;
    for(int i = 1;i <= g[0];i++) {
        memset(f[i&1],0,sizeof(f[i&1]));
        for(int j = 0;j <= n;j++)
        {
            f[i&1][j] += f[i-1&1][j];
            int k = g[i];

            while(j >= k) {
                f[i&1][j] += f[i-1&1][j-k];
                k = k * g[i];
            }
        }
    }
    long long ans = 0;
    for(int i = 1;i <= n;i++) {
        ans += f[g[0]&1][i];
    }
    cout << ans + 1 << endl;
    return 0;
}