LA3641 Leonardo's Notebook

题意

PDF

分析

给出一个26个大写字母的置换B，是否存在A^2 = B

每个置换可以看做若干个循环的乘积。我们可以把这些循环看成中UVa 10294的项链， 循环中的数就相当于项链中的珠子。

A^2就相当于将项链旋转了两个珠子间的距离，珠子0、2、4...构成一个循环，一共有gcd(n, 2)个循环，每个循环的长度为n / gcd(n, 2)

所以当一个循环的长度为奇数的时候，平方以后还是原来的长度；

当一个循环的长度为偶数的时候，平方以后就会分解为两个长度都等于原来循环长度一半的循环。

先将置换B分解循环，对于其中长度为奇数2k+1的循环，可以通过相同长度2k+1的循环平方后从A^2中得到，也可能是2(2k+1)分解出两个2k+1的循环。

但是对于长度为偶数2k的循环来说，一定是由长度为4k的循环平方后分解出来的。

所以如果存在置换A满足A^2 = B，则B中长度为偶数的循环节一定为偶数。

时间复杂度\(O(T\times SIZE)\)

代码

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

co int N=27;

char B[N];

int vis[N],cnt[N],T;

int main(){

//	freopen(".in","r",stdin),freopen(".out","w",stdout);

	read(T);

	while(T--){

		scanf("%s",B);

		memset(vis,0,sizeof vis);

		memset(cnt,0,sizeof cnt);

		for(int i=0,j,n;i<26;++i)if(!vis[i]){

			j=i,n=0;

			do vis[j]=1,j=B[j]-'A',++n;

			while(j!=i);

			++cnt[n];

		}

		int ok=1;

		for(int i=2;i<=26;i+=2)

			if(cnt[i]&1) {ok=0;break;}

		puts(ok?"Yes":"No");

	}

	return 0;

}