首页 > 其他 > 详细

置换群及其应用

时间:2018-08-18 12:37:02      阅读:204      评论:0      收藏:0      [点我收藏+]

置换群是由置换组成的群。即n元集合Ω到它自身的一个一一映射

称为Ω上的一个n元置换或n阶置换

Ω上的置换 技术分享图片 可表示为

技术分享图片

典型例题是POJ2369,给定一个序列,问需要最少需要置换多少次才能变为有序序列

技术分享图片

有了这个定理就可以做题了,我们求出每一个数的最小循环节,求LCM就好了

介绍一下什么是循环节:

1 2 3 4 5

4 1 5 2 3

1->4->2->1

(1,4,2)为一个循环节,长度为3

 1 #include<cstdio>
 2 const int maxn=1005;
 3 int n;
 4 int a[maxn];
 5 int gcd(int a,int b)
 6 {
 7     return b==0?a:gcd(b,a%b);
 8 }
 9 int lcm(int a,int b)
10 {
11     return a/gcd(a,b)*b;
12 }
13 int main()
14 {
15     while(scanf("%d",&n)==1)
16     {
17         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
18         int ans=1;
19         for(int i=1;i<=n;i++)
20         {
21             int tmp=a[i];
22             int cnt=1;
23             while(tmp!=i)
24             {
25                 tmp=a[tmp];
26                 cnt++;
27             }
28             ans=lcm(ans,cnt);
29         }
30         printf("%d",ans);
31     }
32     return 0;
33 }

超级超级简单的模拟

置换群及其应用

原文:https://www.cnblogs.com/aininot260/p/9496707.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!