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。
包含一个整数，可能的排数。
【数据规模和约定】
100%的数据，满足 1 <= N <= 1000 。
首先，我们可以这样思考，每个置换排列都有若干个循环结。e.g. 3 2 1 5 4 6的循环结就是(1,2,3)(4,5)(6)，所以它所能变换的排列数为(lcm为最小公倍数)lcm(1,2,3)=6。而1+2+3=6。
所以我们只需要求出满足x1+x2+x3+x4+...xm=n，lcm(x1,x2,x3,...,xm)有多少种。
蒟蒻的我也只能YY到这里了，暴力枚举肯定没戏，剩下的是题解做的了，其实想想应该是能自己策清的。
首先我们令x1+x2+x3+...+xm<=n(如果少了我们可以补1嘛)。再令x1=p1^t1,x2=p2^t2...其中pi为质数且pi≠pj(i≠j)，则lcm=∏xi，明显不重复。
然后，我们只需要证明若xi=pi*pj，也可以用lcm也包含在上面的情况。
不妨设pi<pj，则因为p是质数，明显有pi*pj>pi+pj，所以对于这种情况我们在pi,pj的情况中枚举了(少了仍然可以补1)。
因此，我们可以dp了，哈哈哈。
f[i][j]表示前i个质数，何为j的方案数(我们都是拆分成pi^ti的形式，刚刚已经证明了其不可能重复，也包含了所有方案)。转移自己脑补一下吧！！！
1 #include<cstdio> 2 #include<cstdlib> 3 using namespace std; 4 5 #define maxn 1010 6 int n,tot,prime[maxn]; long long f[maxn][maxn],ans; bool exist[maxn]; 7 8 inline void find() 9 { 10 for (int i = 2;i <= n;++i) 11 if (!exist[i]) 12 { 13 prime[++tot] = i; 14 for (int j = i*i;j <= n;j += i) exist[j] = true; 15 } 16 } 17 18 inline void dp() 19 { 20 f[0][0] = 1; 21 for (int i = 1;i <= tot;++i) 22 { 23 for (int j = 0;j <= n;++j) f[i][j] = f[i-1][j]; 24 for (int j = prime[i];j <= n;j *= prime[i]) 25 { 26 for (int k = 0;k + j <= n;++k) 27 f[i][k+j] += f[i-1][k]; 28 } 29 } 30 for (int i = 0;i <= n;++i) ans += f[tot][i]; 31 } 32 33 int main() 34 { 35 freopen("1025.in","r",stdin); 36 freopen("1025.out","w",stdout); 37 scanf("%d",&n); 38 find(); 39 dp(); 40 printf("%lld",ans); 41 fclose(stdin); fclose(stdout); 42 return 0; 43 }
原文：http://www.cnblogs.com/mmlz/p/4270839.html
