首页 > 代码库 > P1025[SCOI2009]游戏
P1025[SCOI2009]游戏
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,
问一个n元对称群里的所有置换群，他们各自的x次方等于π0的这个x，有几种可能；
我们知道一个置换群是有许多循环构成的；
于是有：一个对应关系（置换）的所有循环的大小的最小公倍数即是该对应关系（置换）的x，然后一个对应关系（置换）的所有循环的大小的加和不能超过n；
这个东西好像可以用来check一个x；
——对于一个x，把她唯一分解，为
，如果把pi换成sum后，结果小于n，则行数x合法，否则，不合法；
，如果把pi换成sum后，结果小于n，则行数x合法，否则，不合法；（这是在找LCM是x而加和最小的一组数——这组数里的每个数就是一个
——然后check她的加和）
——然后check她的加和）然后这个结论没有二分的性质，于是可以尝试枚举x然后check;
——事实上我一开始就写了这个，然后x可能枚举到很大，就炸了......
于是考虑递推一个方案数;
一个合法方案是指：找一组（质数的幂），其加和小于等于n;
（在原题里的意思是：一个合法方案是一个置换，她的每一个循环都是一个质数的幂，当然可以还剩下一些元素，就让他们子环，但是循环的大小和不能比n大）
由于每一个方案构成的x都不同，所以方案数就是答案；
代码：
#include<cstdio>#include<cstring>using namespace std;const int MAXN=30000001;int prime[MAXN];bool vis[MAXN];int n,cnt;long long f[200][1010];int Prime(int );int main(){ int i,j,k; long long ans=0; scanf("%d",&n); cnt=Prime(n); f[0][0]=1; for(i=1;i<=cnt;i++) for(j=0;j<=n;j++){ f[i][j]+=f[i-1][j]; for(k=prime[i];k<=j;k*=prime[i]) f[i][j]+=f[i-1][j-k]; } for(i=0;i<=n;i++) ans+=f[cnt][i]; printf("%lld",ans); return 0;}int Prime(int n){ int cnt=0; memset(vis,0,sizeof(vis));vis[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]) prime[++cnt]=i; for(int j=1;j<=cnt&&i*prime[j]<=n;j++){ vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } return cnt;}
P1025[SCOI2009]游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。