3641 - Leonardo's Notebook
— I just bought Leonardo’s secret notebook! Rare objectcollector Stan Ucker was really agitated but his friend,special investigator Sarah Keptic was unimpressed.
— How do you know it is genuine?
— Oh, it must be, at that price. And it is written inthe da Vinci code. Sarah browsed a few of the pages. Itwas obvious to her that the code was a substitution cipher,where each letter of the alphabet had been substituted byanother letter.
— Leonardo would have written the plain-text and leftit to his assistant to encrypt, she said. And he must havesupplied the substitution alphabet to be used. If we arelucky, we can find it on the back cover!
She turned up the last page and, lo and behold, therewas a single line of all 26 letters of the alphabet:
QW ERT Y UIOP ASDF GHJKLZXCV BNM
— This may be Leonardo’s instructions meaning that each A in the plain-text was to be replacedby Q, each B with W, etcetera. Let us see. . .To their disappointment, they soon saw that this could not be the substitution that was used in thebook. Suddenly, Stan brightened.
— Maybe Leonardo really wrote the substitution alphabet on the last page, and by mistake hisassistant coded that line as he had coded the rest of the book. So the line we have here is the result ofapplying some permutation TWICE to the ordinary alphabet!
Sarah took out her laptop computer and coded fiercely for a few minutes. Then she turned to Stanwith a sympathetic expression.
— No, that couldn’t be it. I am afraid that you have been duped again, my friend. In all probability,the book is a fake.
Write a program that takes a permutation of the English alphabet as input and decides if it maybe the result of performing some permutation twice.
Input
The input begins with a positive number on a line of its own telling the number of test cases (at most500). Then for each test case there is one line containing a permutation of the 26 capital letters of theEnglish alphabet.
Output
For each test case, output one line containing ‘Yes’ if the given permutation can result from applyingsome permutation twice on the original alphabet string ABC. . .XYZ, otherwise output ‘No’.
Sample Input
2
QWERTYUIOPASDFGHJKLZXCVBNM
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Sample Output
No
Yes
//題意：
給出26個大寫字母的置換B，問是否存在一個置換A，使得A^2=B。
//思路：
設A=(a1 a2 a3)(b1 b2 b3 b4).則：A^2=(a1 a2 a3)(b1 b2 b3 b4)(a1 a2 a3)(b1 b2 b3 b4).==>>(a1 a2 a3)(a1 a2 a3)(b1 b2 b3 b4)(b1 b2 b3 b4)
由置換乘法的結合律，前面兩個循環的乘積和後面兩個循環乘積可以分别算，計算的：
(a1 a2 a3)(a1 a2 a3)=(a1 a3 a2)
(b1 b2 b3 b4)(b1 b2 b3 b4)=(b1 b3)(b2 b4)
由上可以看出規律：兩個長度為n的相同的循環相乘，當n為奇數時結果也是一個長度為n的循環；當n為偶數時分裂為兩個長度為n/2的循環。
是以可以把題中給出的B分解為不相交的循環的乘積。長度n為奇數的循環既可能是兩個長度為n的相同的循環乘出來的，也可能是兩個長度為2n的循環分裂成的，但長度n為偶數的循環隻能是兩個長度為2n的循環分裂成的。是以對于任意偶數長度，循環的個數必須是偶數才能配對。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
#define N 30
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
char b[N];
int vis[N],cnt[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i;
scanf("%s",b);
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
for(i=0;i<26;i++)
{
if(!vis[i])
{
int j=i;
int n=0;
while(1)
{
vis[j]=1;
j=b[j]-'A';
n++;
if(j==i)
break;
}
cnt[n]++;
}
}
int flag=1;
for(i=2;i<=26;i+=2)
if(cnt[i]%2&1)
flag=0;
printf(flag?"Yes\n":"No\n");
}
return 0;
}