大家好，欢迎来到IT知识分享网。
首先介绍一下什么是置换群，不说一些繁琐的概念。
首先给你一个序列，假如：
s = {1 2 3 4 5 6}
然后给你一个变换规则
t = {6 3 4 2 1 5}
就是每一次按照t规则变换下去
比如这样
第一次：6 3 4 2 1 5
第二次：5 4 2 3 6 1
第三次：1 2 3 4 5 6
发现经过几次会变换回去，在变换下去就是循环的了，这就是一个置换群。
我们可以这样表示一个置换群，比如按照上面变化规则
1->6->5->1 那么这些是一个轮换
2->3->4->2 这些是一个轮换
所以可以写为
t = { {1 6 5},{ 2 3 4 } }，然后就衍生出了一些这样的题目
1： nyoj900序列置换
就是求置换群的的一个循环，那么很明显，我们求出置换群中的所有轮换的元素个数，求最小公倍数即可。
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <algorithm> using namespace std; const int N = 300; const int inf = 0x3f3f3f3f; typedef long long LL; int next[N]; bool ok[N]; LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { scanf("%d",&next[i]); } LL ans = 1; memset(ok,false,sizeof(ok)); for(int i=1;i<=n;i++) { if(ok[i]==false) { int tmp = i; LL cnt = 1; ok[i] = true; while(next[tmp]!=i) { cnt++; tmp = next[tmp]; ok[tmp] = true; } LL css = gcd(ans,cnt); ans = (ans*cnt)/css; } } printf("%lld\n",ans); } return 0; }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/29075.html
