置换

置换

一个 $1\sim n$ 的排列 $f$ 可以视作一个长度为 $n$ 的原本排列 $a_1\sim a_n$ 的一个置换

置换 $f$ 的作用是令 $a_i=a_{f_i}$。

记作：

$$f=\left(\begin{array}{c}1,2,3\dots ,n\\ f_1,f_2,f_3,\dots f_n\end{array}\right)$$

乘法

对于两个置换 $f=\left(\begin{array}{c}1,2,3\dots ,n\\ f_1,f_2,f_3,\dots f_n\end{array}\right)$ 和 $g=\left(\begin{array}{c}{f}_1,f_2,f_3\dots ,f_n\\ g_1,g_2,g_3,\dots g_n\end{array}\right)$ 。

$f$ 和 $g$ 的乘积记作 $f\circ g=\left(\begin{array}{c}1,2,3\dots ,n\\ g_1,g_2,g_3,\dots g_n\end{array}\right)$。

排列

一个排列 $p$ 可以看作一个 $a_i\to a_{p_i}$ 的置换。

一个排列经过一个置换后仍然是一个排列。

置换环

一个置换由 $a_i$ 指向 $a_{p_i}$，会形成若干个环：

如 $f=\left(\begin{array}{c}1,2,3,4,5,6\\ 4,6,3,5,1,2\end{array}\right)$

如果通过交换任意两个数字，试图令 $f$ 变成升序排序，则每个环至少需要节点数量 $-1$ 次操作。

草率证明：

交换某个环内部的两个节点的置换（两个节点的出边），则这个环会破解成两个环，最终目的是变成大小为 $1$ 的环，也就是要变出 $circl{e}_i$ 个环。

所以总共需要 $\sum _i(circl{e}_i-1)$ 次操作。

$circl{e}_i$ 为第 $i$ 个环上的节点数量。

设 $cnt$ 是置换环个数

或者表示为 $n-cnt$ 次操作。

逆序数奇偶性

对于交换的两个数字的 $i,j$，假设中间某个数字的位置是 $k$，满足 $i<j<k$。

四种情况：

$a_i<a_k<a_j$ ，交换 $a_i,a_j$ ，和 $k$ 有关的逆序对 $+1+1=2$

$a_i<a_k>a_j$ ，交换 $a_i,a_j$ ，和 $k$ 有关的逆序对 $+1-1=0$

$a_i>a_k<a_j$ ，交换 $a_i,a_j$ ，和 $k$ 有关的逆序对 $-1+1=0$

$a_i>a_k>a_j$ ，交换 $a_i,a_j$ ，和 $k$ 有关的逆序对 $-1-1=-2$

而交换 $a_i$ 和 $a_j$ ，他们的逆序对要么 $+1$ ，要么 $-1$ 。

所以每次交换必定会导致逆序对的奇偶性发生改变。

因为至少要交换 $n-cnt$ 次，所以逆序对的奇偶性和 $n-cnt$ 相同，由此可以 $O(n)$ 求出逆序对的奇偶性。

置换幂次

$f\circ f=f^2$

$f^2$ 是在 $f$ 是置换环的基础上，每一次跳两步，则偶数节点的置换环会拆解成两个环，奇数节点的置换环仍然是一个环。

扩展到 $k$ 次幂，如果环长度是 $t$ ，则会变成 $gcd(k,t)$ 个长度 $\frac{t}{gcd(t,k)}$ 的环。

练习题

Lucky Permutation

Shifting String

E. Tokitsukaze and Two Colorful Tapes

E. Square Root of Permutation

[ABC241E] Putting Candies