[文章目录]
Description
windy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。1 <= N <= 1000
最后排数是所有置换群大小的lcm加1，对于lcm，只有每个质因子的最大次幂有贡献，并且耗费的最少个数提供质因子的k次幂的方案为：构造一个大小为质因子的k次幂的置换。
将每个质因子的某次幂看成物品，大小看成体积，那么答案就是选物品使其体积和不超过N的方案数，跑背包即可。复杂度O(n^2logn)
#include <cstdio>
using namespace std;
typedef long long ll;
int n,pri[1100],cnt;
ll f[1100];
bool v[1100];
void init()
{
int i,j;
for(i=2;i<=n;++i)
{
if(!v[i]) pri[++cnt]=i;
for(j=1;j<=cnt&&i*pri[j]<=n;++j)
{
v[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
int main()
{
scanf("%d",&n);
init();
int i,j,k;
f[0]=1;
for(i=1;i<=cnt;++i)
{
for(k=n;k>=pri[i];--k)
for(j=pri[i];j<=k;j*=pri[i])
f[k]+=f[k-j];
}
ll ans=0;
for(i=0;i<=n;++i) ans+=f[i];
printf("%lld",ans);
return 0;
}