POJ3128 Leonardo's Notebook【置换群】

本文主要是介绍POJ3128 Leonardo's Notebook【置换群】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://poj.org/problem?id=3128

题目大意：

给你一行共 26 个字母，代表一个置换。问：这个置换能否为某个置换平方的结果。

解题思路：

这道题可参考《置换群快速幂运算研究与探讨》，里边有详解。这里放上结论。

结论一： 一个长度为 l 的循环 T，l 是 k 的倍数，则 T^k 是 k 个循环的乘积，每个

循环分别是循环 T 中下标 i mod k=0,1,2… 的元素按顺序的连接。 
结论二：一个长度为 l 的循环 T，gcd(l,k)=1，则 T^k 是一个循环，与循环 T 不一

定相同。

结论三：一个长度为 l 的循环 T，T^k 是 gcd(l,k)个循环的乘积，每个循环分别是循

环 T 中下标 i mod gcd(l,k)=0,1,2… 的元素的连接。 

这倒题中，应用上边的结论来判断这个置换是否为某个置换平方的结果。

一个置换平方可得到：循环节为奇数的置换的平方仍为奇数项的置换，循环节为偶数

的置换的平方分裂成了两个循环节相同的置换。

那么当前置换是由什么置换而来的：

对于奇数项的置换，有可能是由奇数项的置换平方得到的，也有可能是有偶数项的置

换平方得到的。对于偶数项的置换，它一定是原始置换为偶数项的置换分裂得到的。

而且当前置换中偶数项的置换一定成对出现。

那么问题就变为了：对于偶数项的置换，是否成对出现。

那么，我们现在查找 26 个字母的所有置换，计算出每个置换的循环节长度。统计循

环节长度的个数。遍历查找偶数项的置换数目，如果出现奇数，则输出"No"，否则

输出"Yes"。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;char s[33];
bool vis[33];
int ss[33],Cnt[33];int main()
{int T;scanf("%d",&T);while(T--){memset(s,0,sizeof(s));memset(vis,false,sizeof(vis));memset(Cnt,0,sizeof(Cnt));scanf("%s",s);for(int i = 0; i < 26; ++i)ss[i] = s[i] - 'A';int flag = 1;for(int i = 0; i < 26; ++i){if(vis[i] == 0){vis[i] = 1;int temp = ss[i];int num = 1;while(temp != i){vis[temp] = 1;temp = ss[temp];num++;}Cnt[num]++;}}for(int i = 2; i < 26; i+=2)if(Cnt[i]%2){flag = 0;break;}if(flag)printf("Yes\n");elseprintf("No\n");}return 0;
}

这篇关于POJ3128 Leonardo's Notebook【置换群】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---