菜单

ACM暑期培训-POJ-2369

8月 1, 2018 - 算法
ACM暑期培训-POJ-2369

前言

这是一道置换群的问题,第一次见到,记录一下。

题目描述(传送门戳我)

Permutations

We remind that the permutation of some final set is a one-to-one mapping of the set onto itself. Less formally, that is a way to reorder elements of the set. For example, one can define a permutation of the set {1,2,3,4,5} as follows:
This record defines a permutation P as follows: P(1) = 4, P(2) = 1, P(3) = 5, etc. What is the value of the expression P(P(1))? It’s clear, that P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3. One can easily see that if P(n) is a permutation then P(P(n)) is a permutation as well. In our example (believe us)
It is natural to denote this permutation by P2(n) = P(P(n)). In a general form the defenition is as follows: P(n) = P1(n), Pk(n) = P(Pk-1(n)). Among the permutations there is a very important one — that moves nothing:
It is clear that for every k the following relation is satisfied: (EN)k = EN. The following less trivial statement is correct (we won’t prove it here, you may prove it yourself incidentally): Let P(n) be some permutation of an N elements set. Then there exists a natural number k, that Pk = EN. The least natural k such that Pk = EN is called an order of the permutation P.
The problem that your program should solve is formulated now in a very simple manner: “Given a permutation find its order.”

Input
In the first line of the standard input an only natural number N (1 <= N <= 1000) is contained, that is a number of elements in the set that is rearranged by this permutation. In the second line there are N natural numbers of the range from 1 up to N, separated by a space, that define a permutation — the numbers P(1), P(2),…, P(N).
Output
You should write an only natural number to the standard output, that is an order of the permutation. You may consider that an answer shouldn’t exceed 10^9.
Sample Inout
5
4 1 5 2 3
Sample Outout
6


题目大意

来自NYOJ的一道序列置换的题目,题目大意是说,给出一个排列的调整策略,求按照这个策略经过几次操作后可以使其返回原有的序列。

策略的具体含义是指:对于题目给出的序列,有F(1)=4,F(2)=1,F(3)=5,F(4)=2,F(5)=3,经过一次操作,也就是F(F(1)) = F(4) = 2, F(F(2)) = F(1) = 4 等等类推,得到一个新的排列(2 4 3 1 5)如此这样操作下去,第六次之后会回到序列(4 1 5 2 3)


题目分析

这道题本质上是一道置换群的问题,就是求置换群的循环长度,了解过群论的小伙伴们就知道了,只需要求出每一个轮换的元素个数,在去求他们的最小公倍数即可。


这里简单介绍一下轮换的概念,拿样例中的数据来讲第一次操作后3和5换了一次位置,再经过一次操作后就会变回最早的顺序,这就是一个轮换,这个轮换里有两个元素;类似的,对于题目中的序列,(4 1 x 2 x)这一组经过三次操作后,(4 1 2)这三个元素会变回之前的顺序而且与另外两个元素无关,所以(4 1 2)也是一组轮换,它的长度是3,所以对于这个序列来讲,只要变换2*3=6次就可以得到最开始的序列。
也就是说,(4 1 5 2 3)这个排列可以写成(4 1 2)(3 5)的形式


但是在程序里我们并不容易求出每一个轮换以及它们所对应的元素个数,于是在这里我们可以用一个一个找的方法,对于每一个元素,都对他按策略一步一步进行操作直到当前位置的元素与开始时相同,记录这个次数。
当我们记录了每一个次数之后,我们寝室并不需要真正找到某一个轮换,因为每一个轮换里的每一个元素必须经过相同次数(也就是轮换长度)的操作后才能回到之前的位置,而这并不影响这一组数的最小公倍数,所以问题就转化为求这些次数的最小公倍数问题。


具体代码

总结

其实我第一眼看到这个题是懵逼的,要不是今天上午学了一些相关的概念,这道题估计都看不懂,下午也是找了好久的资料,看了一些代码才会写这个题,真是不容易啊,赶紧记下来省的我以后忘了ww

标签:, ,

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注