置换——置换幂与置换开方
BLUEJOKE
·
·
算法·理论
置换
- 一个集合 X 到自身的双射（即一一对应）\sigma 称为 X 的一个置换。如果集合 X 上还有 全序 关系，则它的一个置换也常被称作一个 全排列 。
表示方法
- 双行表示法
集合 X=\{x_{1},x_{2},\dots,x_{n}\} 上的置换可以表示为：\sigma=\begin{pmatrix}x_{1}&x_{2}&\dots&x_{n}\\x_{p_1}&x_{p_2}&\dots&x_{p_n}\end{pmatrix} ，表示置换 \sigma 将元素 x_{i} 映射到 x_{p_{i}} 处。
- 单行表示法
当集合 X 上有自然顺序时，如果在双行表示法中默认首行按照自然顺序（1,2,3\dots）书写，并省略首行，置换可以表示为 \sigma=\sigma(1)\sigma(2)\dots\sigma(n) 。
- 轮换（循环）表示法
将置换表示为一系列不相交的轮换的乘积，步骤如下：
- 写下一个 X 中未写过的 x，在左边添加上左括号。
- 接着不断在右边添加 \sigma(x),\sigma(\sigma(x)),\dots 直到重新等于 x 为止，并添加上右括号。
每一对括号中，都是一个轮换，括号中的元素即为轮换的长度。轮换表示常省略掉长度为一的轮换，恒等变换中所有轮换长度为一，但记作 (1) 而不是省略。
复合
置换的复合就是映射的复合，也被称为置换的乘法。
给定两个置换
\sigma=\begin{pmatrix}x_{1}&x_{2}&\dots&x_{n}\\x_{p_1}&x_{p_2}&\dots&x_{p_n}\end{pmatrix},\pi=\begin{pmatrix}x_{p_1}&x_{p_2}&\dots&x_{p_n}\\x_{q_1}&x_{q_2}&\dots&x_{q_n}\end{pmatrix}
其乘积 \pi\circ\sigma 的值为
\begin{aligned}
\pi\circ\sigma=\begin{pmatrix}x_{1}&x_{2}&\dots&x_{n}\\x_{q_1}&x_{q_2}&\dots&x_{q_n}\end{pmatrix}
\end{aligned}
即 (\pi\circ\sigma)(x)=\pi(\sigma(x))，先经过 \sigma 的映射，再经过 \pi 的映射，复合运算顺序为从右往左，不满足交换律。
逆置换
对任意置换 \sigma，其逆置换 \sigma^{-1} 满足：\sigma\circ\sigma^{-1}=\sigma^{-1}\circ\sigma=e，其中 e 为恒等置换（即对任意 x，e(x)=x）。
给定置换
\sigma=\begin{pmatrix}x_{1}&x_{2}&\dots&x_{n}\\x_{p_1}&x_{p_2}&\dots&x_{p_n}\end{pmatrix}
其逆置换为
\sigma^{-1}=\begin{pmatrix}x_{p_1}&x_{p_2}&\dots&x_{p_n}\\x_{1}&x_{2}&\dots&x_{n}\end{pmatrix}
置换群
群
设 G 是非空集合，其上有二元运算 \cdot ，满足 G\times G\rightarrow G （封闭性），如果满足以下性质，则称 (G,\cdot) 是一个 群 ：
- 结合律：对于所有 a,b,d\in G ，满足 a\cdot(b\cdot c)=(a\cdot b)\cdot c 。
- 存在单位元：存在 e\in G ，对于任意 a\in G ，满足 a\cdot e=e\cdot a=a 。则称 e 为 G 的单位元，也称幺元。
- 存在逆元：对于所有 a\in G ，都存在相应的 b\in G ，满足 a\cdot b=b\cdot a=e 。则称 b 为 a 的逆元。
置换群
- 集合：所有从有限集合 S=\{1,2,\dots,n\} 到自身的双射函数的集合，记作 S_n=<S,\circ> 。
- 运算：置换的 复合 ，即函数的复合运算。
----
# 整幂运算
置换 $T$ 的 $k$ 次幂定义为 $T$ 的 $k$ 次复合：$T^K(x)=T(T(\dots(T(x))))$（共 $k$ 次），用 $T'$ 来表示 $T$ 的轮换表达式，且元素下标从 $0$ 开始。
1. 设 $T$ 为任一置换，其各轮换长度为 $l_1,l_2,\dots,l_m$，若 $T^k=e$，则 $T$ 的阶（最小正整数 $k$ 使得 $T^k=e$)，是 $T$ 的所有轮换长度的最小公倍数 $lcm\big(l_1,l_2,\dots,l_m\big)$。
2. 设 $T'$ 是长度为 $l$ 的单轮换，$d=\gcd(l,k)$，则 $T^k$ 可分解为 $d$ 个互不相交的轮换，第 $i$ 个轮换是轮换 $T'$ 中下标 $idx\ \%\ d=i$ 的元素按顺序的连接。
3. 当 $d=\gcd(l,k)=1$ 时，$(T^{k})'$ 同样为一个长度为 $l$ 的单轮换，首元素固定为 $T’$ 的首元素，则 $(T^k)'\big[i\big]=T'\big[(i+k)\ \%\ l]$。
定义一个长度为 $8$ 的 $T'=(1,6,2,7,8,4,3,5)$，系统性的解释是，将一次置换 $T$ 运算理解为 $T'$ 中的每个元素指代的位置向后跳一步替换到后一个元素指代的位置：
$$1\rightarrow6\rightarrow2\rightarrow7\rightarrow8\rightarrow4\rightarrow3\rightarrow5$$
而 $T^2$ 则为跳两步，由于此时 $\gcd(l,k)=2$，故从一个起点起跳必然不能遍历完所有元素，会提前产生一个更小的轮换，且长度为 $\frac{l}{\gcd(l,k)}$，这就是置换幂的轮换分裂。例如，先从 $0$ 号元素，即 $1$ 开始起跳，得到轮换：
$$(1,2,8,3)=1\rightarrow2\rightarrow8\rightarrow3$$
再从 $1$ 号元素，即 $6$ 开始起跳，得到轮换：
$$(6,7,4,5)=6\rightarrow7\rightarrow4\rightarrow5$$
故 $(T^2)'$ 的轮换表达式为：
$$(1,2,8,3)(6,7,4,5)$$
容易发现，第一个轮换是原轮换表达式中下标符合 $i\equiv0\mod2$ 的元素按序连接的结果，第二个轮换则为符合 $i\equiv1\mod2$ 的元素按序连接的结果。而如果为 $T^3$ 的话则为互质的特殊情况，从一个起点起跳可以遍历到所有元素，此时轮换不会分裂：
$$(1,7,3,6,8,5,2,4)$$
但还是可以注意到 $1,7,3$ 同为下标 $i\equiv0\mod3$ 的元素，$6,8,5$ 同为下标 $i\equiv1\mod3$ 的元素，而由于互质导致最后一个满足 $i\equiv0\mod3$ 的分组 $2,4$ 缺少了一个元素，值得预见的是，$T^5$ 中会有两个分组缺少一个元素，即缺少一个元素的组数为 $\lceil\frac{l}{k}\rceil\times k-l$。
## 练习题及解析
测试链接：[POJ1282 - - 庆典的日期](http://poj.org/problem?id=1282)
题目大意：已知原序列为恒等序列 $e$，给定 $p$ 个置换 $T_0,T_1,\dots,T_{p-1}$，对原序列进行复合运算，第一次计算使用 $T_0$，之后依序使用置换，使用完一轮后又回到 $T_0$。试求最少经过多少次运算后，序列又变回恒等序列。
题目分析：
- 假设存在 $y(y\equiv k\mod p)$ 满足 $T^y(e)=T_k\circ T_{k-1}\circ\dots\circ T_{p-1}\circ\dots T_1\circ T_0\circ T_{p-1}\circ\dots T_1\circ T_0=e$，由于置换的复合满足结合律，取循环节 $T_{step}=T_{p-1}\circ\dots\circ T_1\circ T_0$，可以转换为：$$T^y(e)=T_k\circ\dots\circ T_1\circ T_0\circ T_{step}\circ\dots\circ T_{step}=e$$再取多余元素为 $T_{head}=T_k\circ\dots\circ T_1\circ T_0$，则等价于：$$T_{head}\circ(T_{step})^{\frac{y-k}{p}}=e$$即$$(T_{step})^{\frac{y-k}{p}}=(T_{head})^{-1}$$
- 取 $x=\frac{y-k}{p}$，则等价于求一个最小正整数 $x$，使得 $(T_{step})^x=(T_{head})^{-1}$，考虑 $T_{step}$ 中的一个长度为 $l_i$ 的轮换 $cycle_i$，套用上述的分析和结论。若要使得等式成立，对于该轮换中每个元素都要满足走 $x_i(x\equiv x_i\mod l_i)$ 步能够到达自己对应的逆元处（取模的意义在于走 $l_i$ 步相当于回到起点)，那么其对应的逆元也一定要在这个轮换里。只有满足这两个条件，该轮换才是合法的，而只有当所有轮换都合法时，该 $x$ 才是合法的。
- 对于每一个合法的轮换，若合法则可以得到一个同余方程 $x\equiv x_i\mod l_i$；倘若所有轮换都合法，即可得到同余方程组，再使用中国剩余定理求解即可，最终答案 $y=x*p+k$，总时间复杂度为 $O(p\cdot nlogn)$，其中得到同余方程组的过程为关键优化。
```cpp
#include<iostream>
#include<vector>
#include<cmath>
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int> >
#define pii pair<int, int>
using namespace std;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
ll n, p;
// 扩展欧几里得
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
if(!b) {
x = 1, y = 0, d = a;
return;
}
exgcd(b, a % b, d, y, x);
y -= a / b * x;
}
// 中国剩余定理
ll CRT(vector<pii > &crt, int n) {
ll A = crt[n - 1].x, M = crt[n - 1].y; n--;
ll d, x, y, Mod; // 各个方程的模数不一定互质
while(n--) {
exgcd(M, crt[n].y, d, x, y);
if((A - crt[n].x) % d != 0) return -1; // 方程组矛盾
Mod = crt[n].y / d;
x = ((crt[n].x - A) * x / d % Mod + Mod) % Mod;
A += M * x;
M = M / d * crt[n].y;
}
return A;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
while(cin >> n >> p) {
vvi P(p, vi(n)), T(p, vi(n)), inv(p, vi(n));
for(int i = 0; i < n; i++) {
for(int j = 0; j < p; j++) {
cin >> P[j][i];
P[j][i]--; // 偏移便于模运算
}
}
// 求解 T_step
T[0] = P[0];
for(int i = 1; i < p; i++) {
for(int j = 0; j < n; j++) {
T[i][j] = P[i][T[i - 1][j]];
}
}
// 求解 T_head 的逆元
for(int i = 0; i < p; i++) {
for(int j = 0; j < n; j++)
inv[i][T[i][j]] = j;
}
// 轮换分解
vvi cycle; vi pos(n, -1), idx(n, -1);
int tot = 0;
for(int i = 0; i < n; i++) {
if(pos[i] != -1) continue;
vi rem; int cur = i;
while(pos[cur] == -1) {
pos[cur] = rem.size(), idx[cur] = tot;
rem.pb(cur);
cur = T[p - 1][cur];
}
tot++;
cycle.pb(rem);
}
// 遍历枚举 k 验证等式是否成立
ll ans = LLINF;
for (int i = 0; i < p; i++) {
vector<pii > crt;
bool flag = true;
// 对每个轮换分析是否合法
for(int j = 0; j < tot; j++) {
int k = cycle[j].size(), len = (pos[inv[i][cycle[j][0]]] - pos[cycle[j][0]] + k) % k;
for(int t = 0; t < k; t++) {
if((pos[inv[i][cycle[j][t]]] - pos[cycle[j][t]] + k) % k != len ||
idx[cycle[j][t]] != idx[inv[i][cycle[j][t]]]) {
flag = false;
break;
}
}
if(!flag) break;
crt.pb({len, k});
}
ll x;
if(!flag || (x = CRT(crt, crt.size())) < 0) continue;
ans = min(ans, x * p + i + 1); // 加上偏移量
}
if(ans >= 100000000) cout << "No one knows.";
else cout << ans << endl;
}
return 0;
}
```
## 快速幂计算
如果置换 $T$ 用单行表示法给出，用快速幂思想计算 $A_i=A_{T_i}$ 执行 $k$ 次后的结果，即进行长度为 $n$ 的序列 $A$ 的整幂置换 $T^k(A)$，复杂度为 $O(n\log k)$。
测试连接：[E - Permute K times](https://atcoder.jp/contests/abc367/tasks/abc367_e)
```cpp
const int N;
int n; long long k;
vector<int> A(N), T(N);
vector<int> mul(vector<int> &A, vector<int> &T) {
vi rem(n + 1);
for(int i = 1; i <= n; i++) {
rem[i] = A[T[i]];
}
return rem;
}
vector<int> qpow() {
vector<int> res = A;
while(k) {
if(k & 1) res = mul(res, T);
k >>= 1;
T = mul(T, T);
}
return res;
}
```
如果置换 $T$ 用单行表示法给出，用快速幂思想计算 $T_i=T_{T_i}$ 执行 $k$ 次后的结果，对于第一次运算得到 $T^2$，第二次得到 $(T^2)^2$，那么第 $k$ 次得到 $T^{2^k}$，等价于计算 $T^{2^k}(e)$ 的结果，其中 $e$ 为单位置换。由整幂运算的结论可知，这是每个元素在各自的由 $T$ 拆分出的轮换中跳 $2^k$ 步后的结果，对每个轮换进行快速幂取模运算即可得到对应位置，复杂度为 $O(n\log k)$。
测试链接：[E - Permute K times 2](https://atcoder.jp/contests/abc377/tasks/abc377_e)
```cpp
long long qpow(long long x, long long n, long long k){long long y=1;while(n){if(n&1)y=y*x%k;x=x*x%k;n>>=1;}return y;}
const int N;
int n; long long k;
int T[N], ans[N];
bool vis[N];
void solve() {
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
vector<int> cycle;
int cur = i;
// 轮换分解
while(!vis[cur]) {
vis[cur] = true;
cycle.push_back(cur);
cur = T[cur];
}
int len = cycle.size();
long long off = qpow(2, k, len);
for(int i = 0; i < len; i++) {
ans[cycle[i]] = cycle[(i + off) % len];
}
}
}
```
----
# 置换开方
置换开方为置换幂运算的逆过程，旨在找到置换 $S$，使得 $S^k=T$。
- 若 $\gcd(l,k)=d=1$，此时 $T'$ 为单一轮换，可通过逆过程构造开方置换 $S$，由于 $S^k$ 在前文的理解中为跳跃 $k$ 步，那么从 $T$ 开始向相反方向跳跃 $k$ 步可到达 $S$ 状态，故先构造一个 $ori$ 数组初始化为单位置换，再对 $ori$ 数组模拟跳跃 $k$ 步后变成的轮换表达式，此时轮换 $T[i]$ 原来的位置就是 $ori[i]$，故 $S[ori[i]]=T[i]$，即可得到原置换的轮换 $S'$，
- 若 $T$ 由多个轮换 $C_i$（长度 $l_i$）组成，对于 $T$ 中长度为 $l_i$ 的轮换，需要存在 $d_i$ 个长度为 $\frac{l_i}{d_i}$ 的同构轮换组，才能合并这些小组构造开方置换。构造方法为：将 $d_i$ 个小组的元素依次交叉错位排列，合并为新轮换，再将合并后的新轮换按单轮换开方处理。
## 练习题及解析
测试链接：[P2227 - - [HNOI2001] 洗牌机](https://www.luogu.com.cn/problem/P2227)
题目大意：已知置换 $P$ 经过 $s$ 次 $P=P\circ P$ 复合运算后变为 $T$，现给出 $T$ 和 $s$（保证 $P$ 的长度为奇数，且仅包含一个轮换），求出原序列 $P$。
题目分析：
- 由于置换的长度 $n$ 为奇数，且对 $P$ 做 $s$ 次 $P=P\circ P$ 次复合运算，等价于 $T=P^{2^{s}}$，由于 $\gcd(2^s,n)=1$，那么幂运算不会发生轮换分解，只需要按照上述过程构造原序列即可。
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using ll = long long;
ll qpow(ll x, ll n, ll k){ll y=1;while(n){if(n&1)y=y*x%k;x=x*x%k;n>>=1;}return y;}
const int N = 1e3 + 10;
int n, s;
int T[N], P[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++) {
cin >> T[i];
T[i]--; // 偏移处理便于模运算
}
vi cycle, ori; vector<bool> vis(n);
int cur = 0;
while(!vis[cur]) {
vis[cur] = true;
cycle.pb(cur);
cur = T[cur];
}
s = qpow(2, s, n); // 快速幂计算
// 经过 s 次复合运算后每个元素原来的位置
for(int i = 0, j = 0; i < n; i++) {
ori.pb(j);
j = (j + s) % n;
}
// 轮换还原
for(int i = 0; i < n; i++) {
T[ori[i]] = cycle[i];
}
// 由轮换变为单行表达式
for(int i = 0; i < n; i++) {
P[T[i]] = T[(i + 1) % n];
}
for(int i = 0; i < n; i++) cout << P[i] + 1 << ' ';
return 0;
}
```
另外，由于 $T^n=e$，那么 $\sqrt{T}=\sqrt{T^{n+1}}=T^{\frac{n+1}{2}}$，所以对 $T$ 做 $s$ 次开方运算即可得到 $P$，这是另一种用快速幂方法解决的思路，可在洛谷题解区找到参考代码。
---
# 排列排序最小交换次数
## 排列排序最小交换次数问题
**排列排序最小交换次数问题**：对于一个 $1\sim n$ 的排列 $\{a_1,a_2,\dots,a_n\}$，每次可以交换任意两个数，求将其排序所需的最小交换次数。
- 将该排列看作一个置换 $P=\begin{pmatrix}1&2&\dots&n\\a_1&a_2&\dots&a_n\end{pmatrix}$，对于每个 $i$，将 $i$ 向 $a_i$ 对应的数字连边 $i\rightarrow a_i$，设这样得到的图的中环的个数为 $m$（即该置换的轮换表达式 $P'$ 中轮换的个数 $|P'|$），那么最小交换次数为 $n-m$。
现定义该图中非自环为轮换环，试证明每次交换单个轮换环上的两个元素时会使得所需交换次数减一。
- 当交换的两个元素在同一个轮换环上时：设该轮换环为
$$C:i_1\rightarrow i_2\rightarrow\dots i_k\rightarrow i_1\quad(k\ge2)$$
交换其中任意两个元素 $i_a,i_b(a\lt b)$ 得到两个独立的轮换环
$$\begin{aligned}C_1:&i_1\rightarrow\dots\rightarrow i_a\rightarrow i_{b+1}\rightarrow\dots\rightarrow i_k\rightarrow i_1\\C_2:&i_{a+1}\rightarrow\dots i_b\rightarrow i_{a+1}\end{aligned}$$
因此，交换同一个轮换环上的两个元素后，$m$ 增加 $1$，故 $n-m$ 减少 $1$，当 $m$ 为 $n$ 时，原图中所有轮换环都退化为自环，此时序列恰好为自然排序，$n-m$ 自然为 $0$。
- 当交换的两个元素在任意两个轮换环上时：设两个独立的轮换环为
$$\begin{aligned}C_1:&i_1 \to i_2 \to \dots \to i_a \to \dots \to i_k \to i_1\quad(k\ge2)\\C_2:&j_1 \to j_2 \to \dots \to j_b \to \dots \to j_l \to j_1\quad(l\ge2)\end{aligned}$$
交换 $i_a,j_b(i_a\in C_1,j_b\in{C_2})$ 得到覆盖掉 $C_1,C_2$ 的新轮换环 $$C': i_1 \to i_2 \to \dots \to i_a \to j_{b+1} \to \dots \to j_l \to j_1 \to \dots \to j_b \to i_{a+1} \to \dots \to i_k \to i_1$$此时两个原环合并为为一个新环，总环数 $m$ 相比交换前减少 $1$，故 $n-m$ 增加 $1$，所需交换次数加一。从熵的角度来理解的话，将多个混乱系统合并处理导致熵增后进行处理，比单个单个处理混乱系统更复杂。
## 与逆序对的联系
- 排列中逆序对的奇偶性与排列排序最小交换次数 $n-m$ 的奇偶性相同。
**无论是相邻交换还是任意交换，每执行一次交换，逆序对的奇偶性会翻转，且最小交换次数的奇偶性也会同步翻转**。
1. 相邻交换
- 对逆序对奇偶性的影响：相邻交换仅会改变包含这两个元素的数对的逆序状态，其它数对不受影响。若 $a_k\gt a_{k+1}$，那么逆序对数量减少 $1$；若 $a_k\lt a_{k+1}$，那么逆序对数量增加 $1$。故一次相邻交换必然翻转逆序对的奇偶性。
- 对最小交换次数奇偶性的影响：最小交换次数是 $n-m$，相邻交换对轮换个数 $m$ 的影响只有两种可能。若交换的两个元素位于同一个轮换环上，由前文结论可知 $m$ 增加 $1$；若交换的两个元素在不同轮换环上，由前文结论可知 $m$ 减少 $1$。故一次相邻交换必然翻转最小交换次数 $n-m$ 的奇偶性。
2. 任意交换
- 对逆序对奇偶性的影响：任意交换（交换位置 $i,j(i\lt j)$）可以通过 $2(j-i)-1$ 次相邻交换实现。故一次任意交换必然翻转逆序对的奇偶性。
- 对最小交换次数奇偶性的影响：根据前文可知一次任意交换必然翻转最小交换次数 $n-m$ 的奇偶性。
在自然序列 $(1,2,\dots,n)$ 下，逆序对数和最小交换次数都为 $0$，故从自然序列到达任何一个序列时，该序列的逆序对的奇偶性与排列排序最小交换次数的奇偶性始终相等。