首页 > 代码库 > 【POJ 3128】Leonardo's Notebook
【POJ 3128】Leonardo's Notebook
这道题的问题就是说能否对一个给定的置换进行开方运算
关于这个问题讲的最为详细的是05年集训队论文
潘震皓:《置换群快速幂运算研究与探讨》
对于一个长度为l的轮换,若gcd(l,k)==1,则可以开k方
若gcd(l,k)!=1则对于单个循环是不能开k方的
而若有m个长度为l的轮换,只需要保证gcd(m*l,k)==m就可以
因为开k方是k次方的逆运算,只要保证目标轮换的k次方会分裂成m个数就好了
而若能保证gcd(m*l,k)==m,则m|k,且gcd(l,k/m)==1,即m为k的因子
则最小的m是gcd(l,k)
回到这道题,这道题可以先搜出所有轮换的长度,而因为要求开2次方
因此对于所有奇数长度的轮换是可以开2次方的,对于所有偶数长度的gcd(l,2)==2
因此只要保证,m为2的倍数就行了
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int SIZEN=30; char str[SIZEN]; int a[SIZEN],cnt; bool vis[SIZEN]; int ccnt[SIZEN]; void dfs(int u){ if(vis[u]) return; vis[u]=1;cnt++; //printf("%c ",u+'A'-1); dfs(a[u]); } void solve(){ scanf("%s",str); for(int i=0;i<26;i++) a[i+1]=str[i]-'A'+1; memset(vis,0,sizeof(vis)); memset(ccnt,0,sizeof(ccnt)); int flag=1; for(int i=1;i<=26;i++){ if(!vis[i]){ cnt=0;dfs(i); ccnt[cnt]++; } } for(int i=2;i<=26;i+=2) if(ccnt[i]%2) flag=0; if(flag) printf("Yes\n"); else printf("No\n"); } int main() { int _; scanf("%d",&_); while(_--) solve(); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。