首页 > 代码库 > UVALive - 3641 Leonardo's Notebook（polya计数）
UVALive - 3641 Leonardo's Notebook（polya计数）
题意：给出26个大写字母的置换B，问是否存在一个置换A，使A*A=B？
两个长度为N的相同循环相乘，当N为奇数时结果也是一个长度为N的循环，当N为偶数时分裂为两个长度为N/2的循环。相反，对于一个任意长度为N的奇数循环B，都能找到一个长度为N的循环A使得A*A=B,对于任意两个长度为N（N不一定为偶数）的不相交循环B和C，都能找到一个长度为2N的循环A使得A*A=B*C。
于是只要判断置换B里循环长度相同的且都为偶数(2，4，6, 8.....)的循环个数是不是都为偶数（偶数就能两两配对），只要一个不是的答案就是NO，否则YES。
#include <bits/stdc++.h>using namespace std;char s[26];bool vis[26];int cnt[27],t;int main(){ cin>>t; while(t--){ scanf("%s",s); memset(vis,0,sizeof vis); memset(cnt,0,sizeof cnt); for(int i=0;i<26;i++){ if(vis[i])continue; vis[i]=1; int res=1,tmp=i; while(1){ tmp=s[tmp]-‘A‘; if(vis[tmp])break; vis[tmp]=1; res++; } cnt[res]++; } bool ok=1; for(int i=2;i<=26;i+=2)if(cnt[i]&1)ok=0; printf("%s\n",ok?"Yes":"No"); } return 0;}
UVALive - 3641 Leonardo's Notebook（polya计数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。