计数：Burnside 引理和 Pólya 定理
yingjingxu_NaS2O3
·
2025-03-22 10:36:42
·
算法·理论
群
满足以下条件的集合 G 在集合 G 的二元运算 \cdot 称为一个群：
封闭性：若 a,b\in G ，则存在 a\in G ，使得 a\cdot b=c ；
结合律：对于 \forall a,b,c \in G ，都有 (a\cdot b)\cdot c=a\cdot(b\cdot c) ；
存在单位元：G 中存在一个元素 e ，使得对于 \forall a\in G ，都有 a\cdot e=e\cdot a ；
存在逆元：对于 \forall a\in G ，都有 b\in G ，使得 a\cdot b=b\cdot a=e ，记为 b=a^{-1} 。
置换群
钦定 n 个元素为 1,2,\cdots,n ，若以 a_1\in[1,n] 表示元素 1 ，以 a_2\in[1,n] 表示元素 2 ，……，以 a_n\in[1,n] 表示元素 n ，且 a 为 1\sim n 的一个排列，则用
\end{array}\right)
表示一个置换。
置换的运算 p_1p_2 表示先做 p_1 的置换，再做 p_2 的置换，1,2,3,\cdots,n 的置换集合在该运算下是一个群，故称之为置换群。
循环
我们约定
(a_1a_2a_3\cdots a_n)=\left(\begin{array}{cc}a_1&a_2&a_3&\cdots&a_n\\a_2&a_3&a_4&\cdots&a_1\end{array}\right)
叫做 n 阶循环。
例如
\left(\begin{array}{cc}1&2&3&4&5\\4&3&1&5&2\end{array}\right)=(1\ 4\ 5\ 2\ 3)
\left(\begin{array}{cc}1&2&3&4&5\\3&1&2&5&4\end{array}\right)=(1\ 3\ 2)(4\ 5)
Burnside 引理
最恶心重要的部分。
共轭类
我们约定一个置换分解后 k 阶循环出现的个数为 c_k 个，记为 (k)^{c_k} 。
则一个置换群 S_n 中的置换可按分解成的格式 (1)^{c_1}(2)^{c_2}\cdots(n)^{c_n} 的不同分类，其中若 c_i=0 ，可省略 (i)^{c_i} 不写。
在 S_n 中具有相同格式的置换全体，叫做与该格式相应的共轭类。
k 不动置换类设 G 是 1,2,3,\cdots,n 的置换群（也可以设为 S_n 的一个子群），若 k\in[1,n]\cap\mathbb Z ，则称 G 中使 k 不变的置换全体记为 Z_k 为 G 中使 k 保持不动的置换类，简称 k 不动置换类。
例如 G=\{e,(2\ 3),(1\ 2)(3\ 4),(1\ 2\ 3),(2\ 3\ 4)\} 中使 1 不动的置换类 Z_1=\{e,(2,3),(2,3,4)\} ，其中 e 是单位元，(2\ 3) 为 (1)(2\ 3)(4) 的缩写，下同。
等价类
P1. 对于给定的关于 1,2,3,\cdots,n 的置换群 G ，若存在置换 p\in G 使 k 变为 l ，则存在 p_2=p_1^{-1} \in G 使 l 变为 k 。e 使 k 变为 k 。
P2. 若存在 p_1\in G 使 k 变为 l ，又存在 p_2 使 l 变为 m ，则存在置换 p_3\in p_1p_2\in G 使 k 变为 m ，即对于
k \stackrel{p_1\in G}{\longrightarrow} l \stackrel{p_2\in G}{\longrightarrow} m
有
k \stackrel{p_3=p_1p_2\in G}{\longrightarrow} m
由 P1 和 P2 可知， k 在 G 作用下的“轨迹”形成一个封闭的类，故 \{1,2,3,\cdots,n\} 中的数 k ，若存在置换 p_1 使 k 变为 l ，则称 k 和 l 同属一个等价类。于是 1,2,3,\cdots,n 可按照 G 的置换分成若干个等价类，其中 k 所属的等价类记为 E_k 。
重要定理
定理 1
对于 \forall k \in [1,n]\cap\mathbb Z 都有 |E_k|\ |Z_k|=|G| 。
*证明
钦定 |E_k|=l ，不失一般性，设 E_k=\{a_1(=k),a_2,\cdots,a_l\} ，a_1,a_2,\cdots,a_l 是 l 个不超过 n 的各不相同的正整数，由等价类的定义可知存在 p_i\in G 使得
k\stackrel{p_i}{\longrightarrow}a_i
其中 i\in[1,l]\cap\mathbb Z 。
由于
$$k\stackrel{p\in Z_k}{\longrightarrow}k\stackrel{p_j}{\longrightarrow}a_j$$
故
$$k\stackrel{pp_j=p'_j\in Z_kp_j}{\longrightarrow}a_j$$
同样地，$j\in[1,l]\cap\mathbb Z$。
$G_j=Z_kp_j$ 的元素属于 $G$，而且当 $i\ne j$ 时，$G_i\cap G_j=\emptyset$。
故
$$G_1\sqcup G_2\sqcup G_3\sqcup \cdots \sqcup G_l \subseteq G$$
其中 $A \sqcup B$ 表示不交并，即不相交集合 $A$ 和 $B$ 的并集。
另一方面，对于 $\forall p\in G$ 都有
$$k\stackrel{p}{\longrightarrow}a_j$$
依据 $E_k$，存在 $p_j\in G$，使得 $k\stackrel{p_j}{\longrightarrow}a_j$，所以有
$$k\stackrel{p\in G}{\longrightarrow}a_j\stackrel{p_j^{-1}}{\longrightarrow}k$$
即
$$k\stackrel{pp_j^{-1}}{\longrightarrow}k$$
依据 $Z_k$，有 $pp_j^{-1}\in Z_k$，即 $p\in Z_kp_j$，从而推出 $p\in G_j$。
由于 $p$ 是 $G$ 的任意元素，故
$$G\subseteq G_1\sqcup G_2\sqcup G_3\sqcup \cdots \sqcup G_l$$
则
$$G=G_1\sqcup G_2\sqcup G_3\sqcup \cdots \sqcup G_l$$
故
$$\begin{aligned}|G|&=\sum\limits_{i=1}^l|G_i|\\&=\sum\limits_{i=1}^l|Z_kp_i|\\&=l|Z_k|\\&=|E_k|\ |Z_k|\end{aligned}$$
证毕。
### Burnside 引理
设 $G$ 是 $N={1,2,3,\cdots,n}$ 上的置换群，$G$ 在 $N$ 上可引出不同的等价类，其不同的等价类的个数为
$$l=\frac{\sum\limits_{i=1}^gc_1(a_i)}{|G|}$$
或者写成
$$|X/G|=\frac{\sum\limits_{g\in G}|X^g|}{|G|}$$
#### *证明
不妨作下表，表中的
$$s_{ij}=\begin{cases}1, j\stackrel{a_i\in Z_k}{\longrightarrow}j&\\0,j\stackrel{a_i\notin Z_k}{\longrightarrow}k\ne j\end{cases}$$
故第 $i$ 行求和等于 $c_1(a_i)$，第 $j$ 列求和等于 $|Z_k|$。
$$\sum\limits_{i=1}^{g}\sum\limits_{j=1}^{n}s_{ij}=\sum\limits_{j=1}^{n}|Z_j|=\sum\limits_{i=1}^g c_1(a_i)$$
|$\begin{array}{cc} & & j\\ & s_{ij}\\ a_i &\end{array}$|$\begin{array}{cc}1&2&3&\cdots&n\end{array}$|$c_1(a_i)$|
|:-:|:-:|:-:|
|$\begin{array}{cc}a_1\\a_2\\a_3\\\vdots\end{array}\\a_g$|$\begin{array}{cc}s_{11}&s_{12}&s_{13}&\cdots&s_{1n}\\s_{21}&s_{22}&s_{23}&\cdots&s_{2n}\\s_{31}&s_{32}&s_{33}&\cdots&s_{3n}\\ & &\vdots\\s_{g1}&s_{g2}&s_{g3}&\cdots&s_{g_n}\end{array}$|$\begin{array}{cc}c_1(a_1)\\c_1(a_2)\\c_1(a_3)\\\vdots\\c_1(a_g)\end{array}$|
|$\lvert Z'_j \rvert$|$\begin{array}{cc}\lvert Z'_1 \rvert&\lvert Z'_2 \rvert&\lvert Z'_3 \rvert&\cdots&\lvert Z'_n \rvert\end{array}$|$\sum\limits_{i=1}^gc_1(a_i)=\sum\limits_{j=1}^n\lvert Z'_j \rvert$|
~~我是绝对不会告诉你我一早上只画了这一张表的。~~
若 $N=\{1,2,\cdots,n\}$ 分解为 $l$ 个等价类：
$$N=E_1\sqcup E_2\sqcup E_3\sqcup \cdots E_l$$
当 $j$ 和 $k$ 同属一个等价类时，有 $|Z_j|=|Z_k|$，故
$$\sum\limits_{i=1}^n E_i=\sum\limits_{i=1}^{l}\sum_{j\in E_i} |Z_j|=\sum\limits_{i=1}^l \lvert E_i\rvert\ \lvert Z_i \rvert$$
由于 $|E_i|\ |Z_i|=|G|$（$i\in [1,l]\cap \mathbb Z$），则有
$$\sum\limits_{i=1}^{n}|Z_i|=l|G|$$
$$l=\frac{\sum\limits_{i=1}^gc_1(a_i)}{|G|}$$
# Pólya 定理
设 $\bar G$ 是 $n$ 个对象的一个置换群，用 $m$ 种颜色对 $n$ 个对象染色，则不同的染色方案数为
$$l=\frac{\sum\limits_{i=1}^g m^{c(\bar a_i)}}{|\bar G|}$$
其中 $\bar G={\bar a_1,\bar a_2,\bar a_3,\cdots,\bar a_g}$，$c(\bar a_k)$ 为置换 $a_k$ 的循环节数。
#### *证明
钦定 $n$ 个对象用 $m$ 种颜色进行涂色所得的方案集合为 $S$，显然有 $|S|=m^n$。
$\bar G$ 的每一个元素 $\bar a_{j}$ 对应于 $n$ 个对象的一个排列，也对应了 $S$ 中的 $m^n$ 个涂色方案的一个排列，记作 $a_j$。
这样，$n$ 个对象上的群 $\bar G$，对应于作用在 $S$ 上的群 $\bar G$，故
$$|G|=|\bar G|$$
且有 $c_1(a_j)$=$m^{c(\bar a_j)}$，与前面的证法类似，可得 $S$ 按 $G$ 分成不同等价类的个数为
$$\begin{aligned}l&=\frac{\sum\limits_{i=1}^{g}c_1(a_i)}{|G|}\\&=\frac{\sum\limits_{i=1}^{g}m^{c(\bar a_i)}}{|\bar G|}\end{aligned}$$
证毕。
## *母函数形式的 Pólya 定理
众所周知 Pólya 定理不仅仅能够用来计数。
我们考虑将 Pólya 定理推广到母函数（生成函数）形式，以便对状态进行列举。
设有对象集合 $(a_1,a_2,a_3,a_4)$，用 $(c_1,c_2,c_3)$ $3$ 种颜色来涂染，每个对象着一色，例如 $a_1$ 着 $c_1$ 色，$a_2$ 着 $c_3$ 色，$a_3$ 着 $c_2$ 色，$a_4$ 着 $c_1$ 色，规定对象顺序是 $a_1a_2a_3a_4$，上述着色方案用 $c_1c_3c_2c_1$ 表示。
如果我们不关心具体的对象涂染了什么颜色，只关心方案用了哪些颜色，我们可以进一步写成 $c_1^2c_2c_3$。
例如使用蓝、绿、红、黄这 $4$ 种颜色涂染 $3$ 个同样的球，不妨记为 $b,g,r,y$，所有方案可写为 $(b+g+r+y)^3$，由于 $3$ 个球无区别，故乘法是可交换的。
$$\begin{aligned}(b+g+r+y)^3=\ &b^3+g^3+r^3+y^3+3b^2g+3b^2y+3g^2b+3g^2r\\&+ 3g^2y+3r^2b+3r^2g+3r^2y+3y^2g+3y^2r\\&+ 3y^2b+6bgr+6bgy+6brg+6gry\end{aligned}$$
展开式中的文字项表示方案，系数为方案的数目。
可把上面这种方法应用于 Pólya 定理。
设对 $n$ 个对象用 $m$ 种颜色 $b_1,b_2,b_3,\cdots,b_n$ 进行着色，对应于置换 $a_i$ 的 $k$ 阶$^\dag$**循环因子**，其中 $k$ 个对象，同一颜色用了 $k$ 次，故在
$$l=\frac{\sum\limits_{i=1}^g m^{c(a_i)}}{|G|}$$
中 $m^{c(a_i)}$ 项用
$$(b_1+b_2+b_3+\cdots+b_m)^{c_1(a_i)}(b_1^2+b_2^2+b_3^2+\cdots+b_m^2)^{c_2(a_i)}(b_1^3+b_2^3+b_3^3+\cdots+b_m^3)^{c_3(a_i)}\cdots(b_1^n+b_2^n+b_3^n+\cdots+b_m^n)^{c_n(a_i)}$$
引进循环指数多项式
$$P(G)=\frac{1}{G}\sum\limits_{i=1}^g\prod\limits_{i=1}^n s_k^{c_k(g_i)}$$
$^\dag$循环因子：一个置换分解成若干循环后的其中一个循环。
得
$$P(G)=\frac{1}{|G|}=[s_1^{c_1(a_1)}s_2^{c_2(a_1)}s_3^{c_3(a_1)}\cdots s_n^{c_n(a_1)}+s_1^{c_1(a_2)}s_2^{c_2(a_2)}s_3^{c_3(a_2)}\cdots s_n^{c_n(a_2)}+\cdots+s_1^{c_1(a_g)}s_2^{c_2(a_g)}s_3^{c_3(a_g)}\cdots s_n^{c_n(a_g)}]$$
其中 $s_k=\sum\limits_{i=1}^m c_1^k$（$k\in [1,n]\cap \mathbb Z$）。
证毕。
# 典例
## UVA10733 The Colored Cubes
题目链接：[洛谷](https://www.luogu.com.cn/problem/UVA10733) / [UVa](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1674)
题意：求给一个正方体的六个面涂上 $n$ 种颜色的本质不同方案数。
使正方体重合的刚体运动群，有如下几种情况：
- 不动置换，即单位元素 $(1)(2)(3)(4)(5)(6)$，格式为 $(1)^6$；
- 绕过面 $\alpha_1$ 和 $\alpha_6$ 中心的 $AB$ 轴旋转 $\pm 90\degree$，对应有 $(1)(2\ 3\ 4\ 5)(6)$ 以及 $(1)(5\ 4\ 3\ 2)(6)$，如下图所示：
格式为 $(1)^2(4)^1$，正方体有三个对面，故同类置换有 $6$ 个；
- 绕上图中 $AB$ 轴旋转 $180\degree$ 的置换为 $(1)(2\ 4)(3\ 5)(6)$，格式为 $(1)^2(2)^2$，同类置换有 $3$ 个；
- 绕下图中 $CD$ 轴旋转 $180\degree$ 的置换为 $(1\ 6)(2\ 5)(3\ 4)$，格式为 $(2)^3$，正方体中对角线位置平行的棱有 $6$ 对，故同类置换有 $6$ 个；
- 绕下图中 $EF$ 旋转 $\pm 120\degree$，对应有 $(3\ 4\ 6)(1\ 5\ 2)$ 以及 $(6\ 4\ 3)(5\ 2\ 1)$，格式为 $(3)^2$，正方体的对角线有 $4$ 条，故同类置换有 $8$ 个。
依据 Pólya 定理，
$$l=\frac{\sum\limits_{i=1}^{g}m^{c(\bar a_i)}}{|\bar G|}$$
于是不同染色方案数为
$$\begin{aligned} l&=\frac{1}{24}\times [n^6+6\times n^3+3\times n^4+6\times n^3+8\times n^2]\\&=\frac{n^6+3n^4+12n^3+8n^2}{24}\end{aligned}$$
## P4980 【模板】Pólya 定理
题目链接：[洛谷](https://www.luogu.com.cn/problem/P4980)
依据 Pólya 定理，
$$l=\frac{\sum\limits_{i=1}^{g}m^{c(\bar a_i)}}{|\bar G|}$$
代入 $|\bar G|=n$，$c(\bar a_i)=\gcd(n,i)$ 得
$$l=\frac{\sum\limits_{i=1}^g m^{\gcd(n,i)}}{n}$$
改为枚举 $\gcd$，令 $f(i)=m^i$ 得
$$l=\frac{f * \varphi}{n}$$
其中 $f*g$ 为 $f$ 和 $g$ 的 Dirichlet 卷积。
则有
$$\begin{aligned}l&=\frac{\sum\limits_{d\mid n}f(d)\varphi(\frac{n}{d})}{n}\\&=\frac{\sum\limits_{d\mid n}m^d\varphi(\frac{n}{d})}{n}\end{aligned}$$
代入 $m=n$ 得到
$$l=\sum\limits_{d\mid n}n^{d-1}\varphi(\frac{n}{d})$$
枚举 $d$ 计算贡献即可，时间复杂度 $O(n^{\frac{3}{4}})$。
```cpp
int phi(int n)
{
int ret=1;
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
n/=i;
ret*=(i-1);
while(n%i==0)
{
n/=i;
ret*=i;
}
}
if(n>1)
ret*=(n-1);
return ret;
}
int polya(int m,int n)
{
int ans=0;
for(int i=1;i*i<=n;i++)
if(n%i==0)
{
ans=(ans+phi(i)*quick_pow(m,n/i-1,mod)%mod)%mod;
if(i*i!=n)
ans=(ans+phi(n/i)*quick_pow(m,i-1,mod)%mod)%mod;
}
return ans;
}
```
## 图同构计数问题
### P4727 [HNOI2009] 图的同构计数
题目链接：[洛谷](https://www.luogu.com.cn/problem/P4727)
问题相当于对 $n$ 个无标志顶点的完全图的 $\frac{n(n-1)}{2}$ 条边，用 $2$ 种颜色（分别表示该边存在和不存在）进行着色，求不同方案数的问题。
先 dfs 枚举 $n$ 的拆分再使用 Burnside 求解即可。
```cpp
void Burnside(int n,int b[])
{
int k=0,prod=1;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
k+=__gcd(b[i],b[j]);
for(int i=1;i<=n;i++)
{
k+=b[i]>>1;
prod=prod*b[i]%p;
}
for(int i=1,j;i<=n;i=j)
{
for(j=i;j<=n&&b[i]==b[j];j++)
; // consecutive
prod=prod*fac[j-i]%p;
}
ans=(ans+quick_pow(prod,p-2,p)*quick_pow(m,k,p)%p)%p;
}
int b[105];
void dfs(int cur,int l,int rst) // enum b
{
if(rst<=0)
{
Burnside(cur-1,b); // Burnside
return;
}
for(int i=l;i<=rst;i++)
{
b[cur]=i;
dfs(cur+1,i,rst-i);
}
}
```
另解：使用母函数形式的 Pólya 定理，但是我不太会。
### *P4128 [SHOI2006] 有色图
题目链接：[洛谷](https://www.luogu.com.cn/problem/P4128)
和上一题差不多，把 $2$ 换成 $m$ 即可。
## UVA11255 Necklace
题目链接：[洛谷](https://www.luogu.com.cn/problem/UVA11255) / [UVa](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2222)
依据 Burnside 引理，
$$l=\frac{\sum\limits_{i=1}^gc_1(a_i)}{|G|}$$
显然对于本题我们需要求出 $c_1(a_i)$。
我们考虑 $c_1(a_i)$ 的意义，即在 $a_i$ 作用下保持不动的元素个数。在本题中即为经过一次置换后前后状态本质相同的状态个数。
我们不采用题目中给定的 $n$ 的定义，钦定数据组数为 $t$，令 $n=a+b+c$。
不妨先考虑旋转带来的影响。钦定经过某一种旋转置换后 $d_{(i+k-1)\bmod n+1}\gets d_i$，即将第 $i$ 颗珍珠旋转到第 $(i+k-1)\bmod n+1$ 的位置。
则该置换由 $\gcd(n,k)$ 个长度相等的循环构成，即
$$p=(d_{1,1}\ d_{1,2}\ d_{1,3}\ \cdots\ d_{1,\gcd(n,k)})(d_{2,1}\ d_{2,2}\ d_{2,3}\ \cdots\ d_{2,\gcd(n,k)})\cdots(d_{\frac{n}{\gcd(n,k)},1}\ d_{\frac{n}{\gcd(n,k)},2}\ d_{\frac{n}{\gcd(n,k)},3}\ \cdots\ d_{\frac{n}{\gcd(n,k)},\gcd(n,k)})$$
同时要保证 $\forall i\in [1,\frac{n}{\gcd(n,k)}]\cap \mathbb Z$，$j,k\in [1,\gcd(n,k)]\cap \mathbb Z$ 都有 $d_{i,j}=d_{i,k}$，否则旋转后两个状态本质不同。
不妨令 $t=\frac{n}{\gcd(n,k)}$，则一定有 $t\mid a \land t\mid b\land t\mid c$，若不满足该条件，则无法保证每个环内的颜色相同，方案数为 $0$。
考虑每种颜色的环有多少个。显然，白色环有 $r_a=\frac{a}{t}$ 个，灰色环有 $r_b=\frac{b}{t}$ 个，黑色环有 $r_c=\frac{c}{t}$ 个。
考虑排列这些环的方案数，有
$$s=\frac{\gcd(n,k)!}{r_a!\times r_b!\times r_c!}$$
枚举 $k$ 将贡献累加即可。
然后考虑翻转带来的影响。注意到 $n$ 的奇偶性对翻转前后相同状态的数量以及翻转轴的位置有影响，考虑分类讨论。
$n$ 为奇数时，显然所有翻转轴都是经过一颗珍珠和一段线，如下图所示。
而翻转轴共有 $n$ 条，每一个置换的格式都为 $(1)^1(2)^{\frac{n-1}{2}}$，对经过的珍珠的颜色进行枚举并将贡献累加得到
$$s=n\sum\limits_{i=1}^3\frac{(\frac{n-1}{2})!}{(\frac{a-[i=1]}{2})!(\frac{b-[i=2]}{2})!(\frac{c-[i=3]}{2})!}$$
$n$ 为偶数时，有 $\frac{n}{2}$ 条翻转轴经过两颗珍珠，有 $\frac{n}{2}$ 条翻转轴经过两段线，同样地，翻转轴有 $n$ 条，每一个置换的格式都为 $(1)^2(2)^{\frac{n}{2}-1}$，枚举经过的珍珠的颜色，同样将贡献累加得到
$$s=n\sum_{i=1}^4\frac{(\frac{n}{2}-1)!}{(\frac{a-[i=2]-[i=3]}{2})!(\frac{b-[i=2]-[i=4]}{2})!(\frac{c-[i=3]-[i=4]}{2})!}$$
将所有贡献相加即为 $\sum\limits_{i=1}^gc_1(a_i)$，而 $|G|=2n$，二者相除即为最终答案，注意计算时可能溢出，尽量边乘边除。
```cpp
void dv(__int128 &x,int &a,int &b)
{
if(a)
while(x%a==0)
{
x/=a--;
if(!a)
break;
}
if(b)
while(x%b==0)
{
x/=b--;
if(!b)
break;
}
}
__int128 f(int a,int b,int c,int x)
{
if(a%x||b%x||c%x||a<0||b<0||c<0)
return 0;
a/=x;
b/=x;
c/=x;
int n=a+b+c;
__int128 ret=1;
for(int i=n;i>a;i--)
{
__int128 tmp=i;
dv(tmp,b,c);
ret*=tmp;
dv(ret,b,c);
}
return ret;
}
```
于是主函数的写法就比较显然了。
```cpp
n=a+b+c;
for(int i=1;i<=n;i++)
{
sum+=f(a,b,c,n/__gcd(i,n));
ans+=sum/(n<<1);
sum%=(n<<1);
}
if(n&1)
{
sum+=(f(a-1,b,c,2)+f(a,b-1,c,2)+f(a,b,c-1,2))*n;
ans+=sum/(n<<1);
sum%=(n<<1);
}
else
{
sum+=(f(a,b,c,2)+f(a-1,b-1,c,2)+f(a-1,b,c-1,2)+f(a,b-1,c-1,2))*n;
ans+=sum/(n<<1);
sum%=(n<<1);
}
```
# 编者按
带有*标记的为可跳过部分。
本文在 CSDN 和洛谷同步更新。后续会不会补充未知。
CSDN 链接：https://blog.csdn.net/yingjingxu/article/details/146433892