Permutation Group - 置换群

问题

长度为(n)的序列(s = [x0, x_1, x_2, \cdots, x{n-1} ])上有(n)个数字，每个数字各不相同，且任意的数字都满足(\forall x_i \in [0, n-1])。例如(s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])就是这样一个长度为(10)的序列，拥有(10)个各不相同的数字，且每个数字都满足(i \in [0, 9])。

给出长度相同的序列(t = [y0, y_1, y_2, \cdots, y{n-1} ])，与序列(s)满足相同的条件（有(n)个数字，每个数字各不相同，且任意的数字都满足(\forall y_i \in [0, n-1])）。例如
[t = [3, 4, 2, 6, 1, 7, 0, 5, 9, 8]]
我们将序列(t)作为序列(s)的置换准则，置换操作可以令(s[t[i]] = s[i])，其中(i \in [0, n-1])。将序列(s)中的所有元素按照序列(t)中的下标进行一次置换，称为一次置换操作。例如
[s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
经过序列(t)的一次置换后，变成
[[6, 4, 2, 0, 1, 7, 3, 5, 9, 8]]

求长度为(n)的序列(s)在置换原则t下，经过(k)次置换操作后的元素排列情况。


解法：

暴力(k)次循环时间复杂度过高。我们来仔细考察上面例子中的序列(s)及其置换准则(t)：
[
s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] \
t = [3, 4, 2, 6, 1, 7, 0, 5, 9, 8]
]

((1))对于第(0)个元素，第(1)次置换后(s[0] = 6)；


[ s_1 = [6, 4, 2, 0, 1, 7, 3, 5, 9, 8] ]

((2))对于第(0)个元素，第(2)次置换后(s[0] = 3)；


[ s_2 = [3, 1, 2, 6, 4, 5, 0, 7, 8, 9] ]

((3))对于第(0)个元素，第(3)次置换后(s[0] = 0)；


[ s_2 = [0, 4, 2, 3, 1, 7, 6, 5, 9, 8] ]

((4))对于第(0)个元素，第(4)次置换后(s[0] = 6)；


[ s_2 = [6, 1, 2, 0, 4, 5, 3, 7, 8, 9] ]

我们可以看出第(4)次置换和第(1)置换后(s[0])的结果相同，这说明置换操作是有周期性的，第0个元素(s[0])的周期为3，即(s[0]{i+3} = s[0]{i})，其中(i \in [0, 6])。不同元素的周期是不同的，比如(s[2])的周期为1（(s[2]{i+1} = s[2]{i})，其中(i \in [0, 8])），因为(s[2] \equiv 2)。

经过观察发现任意元素(s[i])都拥有一个循环周期，因此只要确定每个元素的周期，就可以避免暴力循环，直接求出k次置换操作后的序列s。该算法的时间复杂度为(O(n))。