POJ 3128 Leonardo's Notebook[置换群幂相关]

$L e o n a r d o^{'} s <mtext> </mtext> N o t e b o o k$

$D e s c r i p t i o n$
原序列为 ${A, B, C . . . Y, Z}$ ,
请问有没有一种置换 $T$ , 使得连续置换两次得到给出的序列 ${X_{1}, X_{2} . . . X_{N}}$ .

由这篇文章可以得到以下三个结论:

注意结论中的 $T$ 是 循环节,
设符合条件的置换操作前其中一个循环节为 $T$ ,
在这道题目中指数 $k$ 为 $2$ , 于是操作后

若 $T$ 的长度为奇数, 说明 $g c d (s i z e, k)$ 为 $1$ , 则 $T$ 长度不变, 顺序可能会变, 但仍然是一个循环节.
若 $T$ 的长度为偶数, 说明 $g c d (s i z e, j)$ 为 $2$ , 则 $T$ 长度减半, 相当于分裂为两个新的循环节.

所以在给出的序列中, 必须满足 长度为偶数且相等的循环节必须两两配对 才可能被 $T^{2}$ 置换过来.

$C o d e$

#include<cstdio>
#include<cstring>
#define reg register

int A[30];
int sum[30];

char S[30];

bool Used[30];

void Work(){
        scanf("%s", S+1);
        for(reg int i = 1; i <= 26; i ++) A[i] = S[i]-'A'+1;
        memset(Used, 0, sizeof Used);
        memset(sum, 0, sizeof sum);
        for(reg int i = 1; i <= 26; i ++)
                if(!Used[A[i]]){
                        int to = A[i], len = 0;
                        while(!Used[to]) Used[to] = 1, len ++, to = A[to];
                        sum[len] ++;
                }
        for(reg int i = 1; i <= 13; i ++)
                if(sum[i<<1] & 1){ printf("No\n"); return ; }
        printf("Yes\n");
}

int main(){
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}