给出一个26个大写字母的置换B，是否存在A2 = B
每个置换可以看做若干个循环的乘积。我们可以把这些循环看成中UVa 10294的项链， 循环中的数就相当于项链中的珠子。
A2就相当于将项链旋转了两个珠子间的距离，珠子0、2、4...构成一个循环，一共有gcd(n, 2)个循环，每个循环的长度为n / gcd(n, 2)
所以当一个循环的长度为奇数的时候，平方以后还是原来的长度；
当一个循环的长度为偶数的时候，平方以后就会分解为两个长度都等于原来循环长度一半的循环。
先将置换B分解循环，对于其中长度为奇数2k+1的循环，可以通过相同长度2k+1的循环平方后从A2中得到，也可能是2(2k+1)分解出两个2k+1的循环。
但是对于长度为偶数2k的循环来说，一定是由长度为4k的循环平方后分解出来的。
所以如果存在置换A满足A2 = B，则B中长度为偶数的循环节一定为偶数。
#include <cstdio>
#include <cstring> int main()
{
//freopen("in.txt", "r", stdin); int T;
scanf("%d", &T);
while(T--)
{
char s[];
scanf("%s", s);
bool vis[];
memset(vis, false, sizeof(vis));
int cnt[];
memset(cnt, , sizeof(cnt)); for(int i = ; i < ; i++) if(!vis[i])
{
int j = i;
int n = ;
do
{
vis[j] = ;
n++;
j = s[j] - 'A';
}while(j != i);
cnt[n]++;
} bool ok = true;
for(int i = ; i <= ; i += ) if(cnt[i] & ) { ok = false; break; }
printf("%s\n", ok ? "Yes" : "No");
} return ;
}
代码君