题目
题目描述
windy学会了一种游戏。
对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。
最开始windy把数字按顺序1，2，3，……，N写一排在纸上。
然后再在这一排下面写上它们对应的数字。
然后又在新的一排下面写上它们对应的数字。
如此反复，直到序列再次变为1，2，3，……，N。
如： 1 2 3 4 5 6
对应的关系为
1->2 2->3 3->1 4->5 5->4 6->6
windy的操作如下
1 2 3 4 5 6
2 3 1 5 4 6
3 1 2 4 5 6
1 2 3 5 4 6
2 3 1 4 5 6
3 1 2 5 4 6
1 2 3 4 5 6
这时，我们就有若干排1到N的排列，上例中有7排。
现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。
输入输出格式
输入格式：
一个整数，N。
输出格式：
一个整数，可能的排数。
输入输出样例
输入样例#1：
3
输出样例#1：
3
输入样例#2：
10
输出样例#2：
16
说明
30%的数据，满足 1 <= N <= 10 。
100%的数据，满足 1 <= N <= 1000 。
题解
这题其实跟群论没什么关系…
可以发现，排数=所有的循环节的$lcm$
就拿题目中的栗子来说,循环节为
并且循环节循环ta的长度次就会回到原点
所以排数$=lcm(3,2,1)=6$
还有初始的1排所以为7（其实加不加无所谓因为是统计方案）
所以问题就转化为总和为$n$的一堆数的$lcm$种类
发现枚举质因数和指数就行了
问题最后变为完全背包问题，即容量为$n$，物品为质因数，求装的方案
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# define LL long long
using namespace std;
const int MAX=1e3+1;
int n,tot;
LL ans;
int pm[MAX];
LL f[MAX][MAX];
bool use[MAX];
int main()
{
scanf("%d",&n);
if(n==1) return printf("1"),0;
for(int i=2;i<=n;++i)
{
if(!use[i]) pm[++tot]=i;
for(int j=1;j<=tot&&pm[j]*i<=n;++j)
{
use[pm[j]*i]=1;
if(i%pm[j]==0) break;
}
}
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=pm[i];j<=n;j*=pm[i])
for(int k=0;k<=n-j;++k)
f[i][k+j]+=f[i-1][k];
if(i==tot)
for(int j=0;j<=n;++j)
ans+=f[i][j];
}
return printf("%lld",ans),0;
}
