传送门
要将所有置换变成一个轮换，显然轮换的周期是所有置换长度的最小公倍数。
于是我们只需要求长度不超过n，且长度最小公倍数为t的不同置换数。
而我们知道，lcm只跟所有素数的最高位有关。
因此lcm=∏iprimeipi" role="presentation" style="position: relative;">∏iprimeipi∏iprimeipi 。
于是我们可以定义状态f[i][j]表示前i个素数凑出的和为j的方案数。
这个可以用类似于背包的算法处理。
于是就愉快的做完了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;
int n,pri[N],tot=0;
bool vis[N];
ll f[N][N],ans=0;
inline void init(int len){
for(int i=2;i<=len;++i){
if(!vis[i])pri[++tot]=i;
for(int j=1;j<=tot;++j){
int k=pri[j]*i;
if(k>len)break;
vis[k]=true;
if(i%pri[j]==0)break;
}
}
}
int main(){
cin>>n,init(n);
f[0][0]=1;
for(int i=1;i<=tot;++i){
for(int j=0;j<=n;++j)f[i][j]=f[i-1][j];
for(int j=pri[i];j<=n;j*=pri[i])for(int k=0;k<=n-j;++k)f[i][j+k]+=f[i-1][k];
}
for(int i=0;i<=n;++i)ans+=f[tot][i];
cout<<ans;
return 0;
}