hrbust oj 1536 Leonardo's Notebook 置换群问题

题目大意：

给出一个A~Z的置换G，问能否找到一个A~Z的置换G' 能够用来表示为 G = G'*G'

由定理：

任意一个长为 L 的置换的k次幂，都会把自己的每一个循环节分裂成gcd(L, K)份，并且每一份的长度都为L/gcd(L,K)

这里是置换的平方，所以G'长度为偶数的循环节必然会分裂为两个相等的循环节，长度为奇数的循环节还是一个循环节长度不变

那么得到的G中长度为偶数的循环节必然是由G'中偶数的循环节分裂得到，奇数的循环节可以不多做考虑，就认为它是原来的奇数循环节保持不变所得

所以这里只要判断G中数量为偶数的循环节能否做到两两配对即可

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int cnt[] , to[] , vis[];

 char str[];

 void solve(int u)

 {

     int ans =  , v = u;

     while(u != to[v]){

         vis[v] = ;

         ans++;

         v = to[v];

     }

     vis[v] = ;

     cnt[ans]++;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int T;

     scanf("%d" , &T);

     while(T--)

     {

         scanf("%s",  str);

         //建立映射关系

         for(int i= ; i< ; i++){

             to[i+] = str[i]-'A'+;

         }

         memset(cnt ,  , sizeof(cnt));

         memset(vis ,  , sizeof(vis));

         for(int i= ; i<= ; i++){

             if(!vis[i]) solve(i);

         }

         int flag = ;

         //遇到任何一个循环节为偶数的不能配对的情况就会输出No

         for(int i= ; i<= ; i++){

             if(cnt[i] && !(i&)){

                 if(cnt[i]&){

                     flag = ;

                     break;

                 }

             }

         }

         if(flag) printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }