给出26个大写字母组成 字符串B问是否存在一个置换A使得A^2 = B
书上的证明结论
2个长度为n的相同循环相乘 n为奇数时结果为1个长度为n的循环 n为偶数时分裂成2个长度为n/2的循环
倒过来
对于一个长度为n为奇数的循环B都能找到一个长度为n的循环A使得A^2 = B 对应任意2个长度为n的不相交循环B,C 都能找到一个长度为2n的循环A 使得A^2 = BC
所以对于B=(1,3,4)(2,5)(6,9)(7,8)输出No 因为长度为偶数的循环有奇数个
以上白书有介绍
对于输入的B 算出所有循环的长度 在判断一下 长度为偶数的是否有偶数个
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
char s[30];
int vis[30], cnt[30], T;
scanf("%d", &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])
{
int j = i,n = 0;
do
{
vis[j] = 1;
j = s[j] - ‘A‘;
n++;
}
while(j != i);
cnt[n]++;
}
}
int ok = 1;
for(int i = 2; i <= 26; i += 2)
if(cnt[i]%2)
ok = 0;
if(ok)
puts("Yes");
else
puts("No");
}
return 0;
}