==== 理论 ====
=== 置换的定义 ===
设$X$是有限集。不失一般性，取$X$为有前n个正整数组成的集合$\{1,2,...,n\}$。$X$的**置换**$i_1,i_2,...,i_n$可以看成是$X$到自身的一一映射，其定义为：
$$f:X\to X$$
其中$$f(1)=i_1,f(2)=i_2,...,f(n)=i_n$$
为了强调其可视性，常用$2\times n$的阵列来表示这个置换，如：
$$\left( \begin{array}{c} 1 &2 &... &n\\i_1 &i_2 &... &i_n\end{array} \right)$$

=== 置换群的定义 ===

把有n个元素的集合$\X={1,2,...,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$为单循环时，则$T^k=\iota$的最小正整数解为$T$的循环长度$l$

对置换的整幂运算$T^n$，感觉用快速幂$O(nlogk)$就行（<del>其实是因为论文中的算法没看懂</del>

对置换的分数幂运算（开方）
分两种情况：

单循环：如果循环长度和指数互质则能开方，否则不能

多循环：取$m=gcd(l,k)$个长度相同的循环合并，如果某个长度的循环数不能被$m$整除则不能开方

==== 题目 ====
1、置换群中的循环

[[https://vjudge.net/problem/POJ-1026|poj1026 Cipher]]

每次给出一个置换，再给出多个字符串，如果字符串长度为$k$则对字符串的下标置换k次（空出来的地方填空格），然后输出新的字符串

不用置换群的知识就硬模拟都行，找出置换群里的每个循环，然后模拟即可

[[https://vjudge.net/problem/POJ-3270|poj3270 Cow Sorting]]

一个两两不同的序列$a[i]$，可以交换$a[i],a[j]$的值，花费为$a[i]+a[j]$，问如何花费最少的代价使得序列边为升序

记排序后的序列的下标序列为$p$，则可以构造原下标对应$p$一个置换
$$\left (\begin{array}{c} 1&2&...&n\\p_1&p_2&...&p_n\end{array}\right)$$
求出置换中所有的循环，考虑每个循环中交换的花费。记某个循环中所有下标对应最小的值为$mi$，循环长度为$len$，该循环中所有下标对应值的和为$sum$，所有序列中的最小值为$low$，则每个循环的最小花费为$$min\{sum+mi\times (len-2),\; sum+mi+low\times (len+1)\}$$
其含义为：每个循环中的最小元素分别去交换其他元素使得其他元素在合适位置，或者先让循环内的最小元素和全局的最小元素交换再分别交换循环内的其他元素，结束后重新交换回循环内的最小元素。正确性挺显然的（bushi

[[https://vjudge.net/problem/UVA-11077|uva11077 Find the Permutations]]

问长度为n的所有排列里有多少种排列能在最少交换$m$次的情况下变成$1,2,...,n$

把每个排列都看出一个置换，最少交换次数的贡献来源于置换中的每个循环，交换次数=每个循环的长度-1的和

定义$f[i][j]:=长度为n的所有排列中，最少交换次数为j的排列个数$，于是有$f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1)$

[[https://vjudge.net/problem/POJ-3590|poj3590 The shuffle Problem]]

问长度为$n$的置换$T$，使得$T^k=\iota$的最小正整数解$k$最大的$T$是什么

有上述定理可知$T^k=\iota$的最小正整数解为$T$中所有循环的最小公倍数，这个显然能通过$\text{dp}$求得。记$f[i][j]:=和为i的j个数的lcm$，于是$f[i][j]=max\{f[i-1][j-k]*k/gcd(f[i-1][j-k],k)\}$

从而能得到长度为$n$的置换的解$\text{maxlcm}$,并唯一分解得到$maxlcm=\prod p_i^{k_i}$且$\sum p_i^{k_i}\le n$，所以拆成大小为$p_i^{k_i}$的循环，剩下的都是长度为1的循环即可

2、置换群的幂运算

[[https://www.luogu.com.cn/problem/P2227|P2227 洗牌机]]

已知$T^{2^s}$求$T$，保证$T$为单循环且长度为奇数

相当于$T$做了平方运算后，再讲得到的新置换继续平方，一共操作$s$次。因为长度为奇数，所以平方过程中不会分裂，始终保持单循环。再由定理$T^k=\iota$的解是$l$的整数倍，所以如果有$2^t \equiv 1 \pmod l$，那么$T^{2^t}=T$，即$T^{2^{(t-s\%t)}}=T$

又$2^t \equiv 1 \pmod l$在小于$l$的范围内一定有解，所以可以在$O(nlogn)$下求解

还有另一种思路是由$T^{(l+1)}=T$，所以$T^{\frac 12}=(T^{\frac 12})^{(l+1)}=T^{\frac{l+1}2}$，记$R=T^{2^s}$，则$T=(R^{\frac{l+1}2})^s$