置换群

关于置换群在acm中的应用最典型的就是2004年潘震皓在国家集训队的一篇论文《置换群快速幂运算 研究与探讨》。题目有poj1721、poj1026、poj3270，cf287C。
关于群的理论和置换的一些理论：
定理1:任何一个置换都可以表示成若干循环的乘积。
定理2：任何一个循环都可以表示成若干换位之积。(二阶循环(i,j)叫做i和j的对换或者换位)
如：\((1 3)(1 2)=\left(
\begin{array}{ccc}
1 & 2 & 3 \\
2 & 1 & 3
\end{array}
\right) \left(
\begin{array}{ccc}
1 & 2 & 3 \\
3 & 2 & 1
\end{array}
\right) = \left(
\begin{array}{ccc}
1 & 2 & 3 \\
2 & 1 & 3
\end{array}
\right) \left(
\begin{array}{ccc}
2 & 1 & 3 \\
2 & 3 & 1
\end{array}
\right) = \left(
\begin{array}{ccc}
1 & 2 & 3 \\
2 & 3 & 1
\end{array}
\right) = (1 2 3)\)

性质：任何一个置换分解为换位的个数是不定的，但是奇偶数是固定的。
如：\(\left(
\begin{array}{ccc}
1 & 2 & 3
\end{array}
\right)=\left(
\begin{array}{cc}
1 & 2
\end{array}
\right) \left(
\begin{array}{cc}
1 & 3
\end{array}
\right)=\left(
\begin{array}{cc}
1 & 2
\end{array}
\right) \left(
\begin{array}{cc}
1 & 3
\end{array}
\right) \left(
\begin{array}{cc}
3 & 1
\end{array}
\right) \left(
\begin{array}{cc}
1 & 3
\end{array}
\right)\)

性质2: \(p= \left(
\begin{array}{cccc}
a_1 & a_2 & \cdots & a_n
\end{array}
\right)\),则\(p^n=(1)(2) \cdots (n) =e\)

潘震皓论文的结论:
1.置换群的乘方:求T^k(k为正整数)
对于置换T,用数组a[i][]表示置换T的循环,约定a[i][0]为该循环内最小的数,且l[i]表示对应循环的长度.
对每个循环,若l[i]是k的倍数,则乘方之后分裂为k个循环,并且每个循环分别是循环a[i]中下标j mod k = 0, 1, 2….的元素按顺序连接.
对每个循环,若gcd(l[i],k) = 1,则乘方之后仍然是一个循环,设原循环为数组a[i],长度为l[i],乘方之后为a[i]’ ,则a[i]'[j] = a[i][k*j mod l[i]].
对每个循环,若不为上面两种情况,则乘方之后为gcd(l[i], k)个循环的乘积,每个循环分别是原循环a[i]中下标j mod gcd(l[i], k) = 0, 1, 2…的元素的连接.

2.置换群的开方:求T^(1/k)(k为正整数)
a.若置换为单循环置换,且循环长度与指数k互质,则由上面第二种情况的公式可以逆推得到.
b.若置换为单循环置换,但循环长度与指数k不互质,则由上面的结论可以知道,这是不能开方的.
c.若置换不为单循环置换,则对l[i]中任意一个有执行以下操作:
①1.令m = gcd(i[i],k);
②.选择n*m份长度均为l[i]的循环进行合并,其中n为整数且n*m为k的约数;
③.将形成的大循环开k/m次方.