1025: [SCOI2009]游戏

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2727 Solved: 1794
[Submit][Status][Discuss]

Description

　　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想知道，对于所有可能的对应关系，有多少种可
能的排数。

Input

　　包含一个整数N,1 <= N <= 1000

Output

　　包含一个整数，可能的排数。

Sample Input

【输入样例一】
3
【输入样例二】
10

Sample Output

【输出样例一】
3
【输出样例二】
16

这其实更像一道数学题。。。

以题目中N=6为例：

1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6

可以划分为(1,2,3) (4,5) (6) 三个循环节，模拟计算几组数据后发现都可以划分为这样的循环节

循环节的长度之和正好等于N，(即：3+2+1=6)，而一个可能的排数等于LCM(循环节长度)，即所有循环节长度的公倍数+1

因此问题转化为：和为N的一串数，求它们的最小公倍数，而这一串数可以继续分解成更小的数(即这一串数不是固定的），并继续求最小公倍数，所有可能的最小公倍数的总数，即为方案数

如：

一串数　　　　最小公倍数

6　　　　　　　　6

5 1　　　　　　　5

4 2　　　　　　　4

4 1 1　　　　　　 4

3 3　　　　　　　3

。。。。。。

最终可以发现可行的最小公倍数是：1，2，3，4，5，6，这六种，因此答案为6

而怎么求这一串数又成了问题，这里可以反过来思考，一个可行的最小公倍数需要满足的条件。

最小公倍数一定是一个合数，而一个合数可以分解为多个质数的积，那么最小公倍数的一个因数就是多个质数相乘后的积，并且需要满足所有因数的和小于等于N

因此可以得到最小公倍数Z=a1^b1 × a2^b2 × a3^b3 × ...（a为质数），如6=3^1 × 2^1

等于N我们都知道，至于为什么可以小于N，假设N=6为例，其中一种可行的最小公倍数，6=3^1×2^1，而3+2≤6。

因为作为这一串数：

一串数　　　　最小公倍数

3 2 1　　　　　　 6

可以补1这种情况。

接下来就要用到动态规划，设f[i][j]，i表示前i个质数，j表示因数的和，表示前i个质数，因数和小于等于N的情况总数

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define LL long long

 const int MAXN=;

 int cnt=,prime[MAXN];

 int n;

 LL ans,f[][];

 void Prime(int x)

 {

     bool mark[MAXN];

     for(int i=;i<=x;i++)

     {

         if(!mark[i]) prime[++cnt]=i;

         for(int j=;j<=cnt&&prime[j]*i<=x;j++)

         {

             mark[prime[j]*i]=;

             if(i%prime[j]==) break;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     Prime(n);

     f[][]=;

     for(int i=;i<=cnt;i++)

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

         {

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

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

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

         }

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

         ans+=f[cnt][i];

     cout<<ans<<endl;

     return ;

 }

巴特西