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;
}