[SCOI2009]游戏

Time Limit:1000MS Memory Limit:165536K
Total Submit:15 Accepted:11

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。

Output

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

Sample Input

Sample Output

Source

Day1
这道题目很明显就是给你一个N，然后求在和的N的数列中，最小公倍数有几种可能的情况。
很明显如果一个数A=p1^a1*p2^a2*….的话，他能被表达出来的充分必要条件是：
p1^a1+p2^a2+…..<=N这是很好证明的，就不说了。那么很显然就变成一个DP的问题了。
设F(i,j)为第i个素数开始和小于j有多少情况，具体看代码把(*^__^*) 。。这可以说是一道数学问题了。。看来数学学多了也是有好处的囧。。
Code：

#include<iostream>using namespace std;const int maxn=1000+100;bool IsPrime(int p){ if(p==2) return true; if(p%2==0) return false; for(int x=3;x*x<=p;x+=2) if(p%x==0) return false; return true;}int Ps[maxn],cnt=0,n;void GetPrime() //直接写暴力了，懒得写筛法了。。{ for(int x=2;x<=n;x++) if(IsPrime(x)) Ps[cnt++]=x;}typedef long long ll;ll F[maxn][maxn];bool s[maxn][maxn]={0};ll dfs(int pos,int N) //记忆化搜索 pos-cnt的素数，和小于N有多少种情况{ if(pos==cnt&&N>=0) return 1; //边界情况 ll&ans=F[pos][N]; //用引用比较方便 if(s[pos][N]) return ans; ans=0;s[pos][N]=true; for(int x=Ps[pos];x<=N;x*=Ps[pos]) //枚举第pos个素数的幂数 { ans+=dfs(pos+1,N-x); } ans+=dfs(pos+1,N); //如果不选这个素数的话 return ans;}int main(){ cin>>n;GetPrime(); cout<<dfs(0,n)<<endl;}【输出样例一】3【输出样例二】16【数据规模和约定】30%的数据，满足 1 <= N <= 10 。100%的数据，满足 1 <= N <= 1000 。【输入样例一】3【输入样例二】10