标题效果：特定n。行定义一个替代品1~n这种更换周期发生后，T次要(T>0)返回到原来的顺序 找到行的所有可能的数

循环置换分解成若干个，然后行位移数是这些周期的长度的最小公倍数

因此，对于一些，是将这个数分解质因数。令x=p1^a1*p2^a2*...*pk^ak。若p1^a1+p2^a2+...+pk^ak<=n，则x就是可能的排数

分组背包就可以 令f[i][j]表示用前i个质数，和为j能得出的数的数量 每组的物品是pi^1~pi^ai

时间复杂度O(n/lgn*logn*n)=O(n^2)

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 1010

using namespace std;

typedef long long ll;

int n,prime[M],tot;

bool not_prime[M];

ll f[M][M],ans;//f[i][j]表示用前i个质数。和为j能得出的数的数量

void Linear_Shaker()

{

	int i,j;

	for(i=2;i<=n;i++)

	{

		if(!not_prime[i])

			prime[++tot]=i;

		for(j=1;j<=tot&&prime[j]*i<=n;j++)

		{

			not_prime[prime[j]*i]=1;

			if(i%prime[j]==0)

				break;

		}

	}

}

int Quick_Power(int x,int y)

{

	int re=1;

	while(y)

	{

		if(y&1)re*=x;

		x*=x;

		y>>=1;

	}

	return re;

}

int main()

{

	int i,j,k,temp;

	cin>>n;

	Linear_Shaker();

	f[0][0]=1;

	for(i=1;i<=tot;i++)

	{

		for(j=0;j<=n;j++)

			f[i][j]+=f[i-1][j];

		for(j=prime[i];j<=n;j*=prime[i])

			for(k=j;k<=n;k++)

				f[i][k]+=f[i-1][k-j];

	}

	for(i=0;i<=n;i++)

		ans+=f[tot][i];

	cout<<ans<<endl;

	return 0;

}