理论
置换的定义
设$X$是有限集。不失一般性，取$X$为有前n个正整数组成的集合$\{1,2,\ldots,n\}$。$X$的置换$i_1,i_2,\ldots,i_n$可以看成是$X$到自身的一一映射，其定义为： $$f:X\to X$$ 其中$$f(1)=i_1,f(2)=i_2,\ldots,f(n)=i_n$$ 为了强调其可视性，常用$2\times n$的阵列来表示这个置换，如： $$\left( \begin{array}{c} 1 &2 &\ldots &n\\i_1 &i_2 &\ldots &i_n\end{array} \right)$$
置换群的定义
把有n个元素的集合$\X={1,2,\ldots,n\}$的所有$n!$个置换构成的集合记为$S_n$，则如果$S_n$中的非空子集$G$满足如下三条性质，则定义它为$X$的置换群： (1)合成运算的封闭性：$\forall f,g\in G,f\circ g\in G$ (2)单位元：$S_n$中的恒等置换$\iota \in G$ (3)逆元的封闭性：$\forall f\in G,f^{-1}\in G$
特别的$S_n$是一个置换群，称它为$n$阶对称群，仅有一个恒等置换的集合$G=\{\iota \}$也是一个置换群。
置换群都满足消去律： $$f\circ g=f\circ h \; \leftrightarrow \; g=h$$ 因为用$f^{-1}$左乘等式两端，并通过结合律，则得证
置换的幂运算
参考文献: 《2005信息学国家集训队论文：置换群快速幂运算 研究与探讨》——潘震皓
对任意置换$T$，可对其进行循环分解，如 $$f=\left (\begin{array}{c} 1&2&3&4&5&6&7&8\\6&8&5&4&1&3&2&7\end{array}\right)=[1\;6\;3\;5]\circ[2\;8\;7]\circ[4]$$ 显然有如下性质：对置换$T$，$T^k=\iota$的最小正整数解为$T$中所有循环长度的最小公倍数
对置换的整幂运算$T^n$，感觉用快速幂$O(nlogk)$就行惹（~~其实是因为论文中的$O(n)$算法没看懂~~
对置换的分数幂运算（开方）就很有意思了 分两种情况： 循环长度和指数互质：
