OI 中的群论

什么是群

• 操作之间可以进行复合，且依然得到 $G$ 中的元素。
• 存在什么都不做的操作。
• 操作可逆。

群

二元组 $(G, \star)$ 称为 群，若集合 $G$ 在二元运算 $\star: G\times G\to G$ 下：

• 满足结合律 $a\star (b \star c) = (a\star b)\star c$。
• 存在单位元 $e$ 满足对任意 $a\in G$，$e\star a = a\star e = a$。
• 任意 $a\in G$ 存在逆元 $a ^ {-1}$，满足 $a\star a ^ {-1} = a ^ {-1}\star a = e$。

可以证明 逆元唯一。

一般 $e$ 记为 $1$ 且省略 $\star$ 不写。

群作用

群作用

映射 $\cdot : G\times A\to A$ 是群 $G$ 在集合 $A$ 上的 群作用，若：

• 对任意 $g_1, g_2\in G$ 和 $a\in A$，都有 $g_1\cdot (g_2 \cdot a) = (g_1g_2) \cdot a$。
• 对任意 $a\in A$，都有 $1\cdot a = a$。

可以证明 $g$ 作用在不同的元素上，得到的元素也是不同的。将 $g : a\mapsto g\cdot a$ 看成 $A\to A$ 的映射，那么 $g$ 有逆映射 $g ^ {-1}$，因为 $(gg ^ {-1}) \cdot a = 1\cdot a = a$。因此，$g$ 一定是双射。

为什么要学习群

轨道 orbit

考虑 $G$ 作用在 $A$ 上（作用不一定唯一）。对 $a\in A$，$\{g\cdot a\mid g\in G\}$ 称为 $a$ 的 轨道。

群公理所保证的良好性质使得群作用的轨道是等价关系。简单地说，如果 $b = g\cdot a$ 在 $a$ 的轨道内，那么 $a = g ^ {-1}\cdot b$ 也在 $b$ 的轨道内。所以 $A$ 中两个元素的轨道要么不交，要么相等。又因为每个元素属于它自己的轨道，所以在给定作用下，$G$ 将 $A$ 划分（每个元素恰属于一个集合）为了若干轨道 $\mathcal O_1, \mathcal O_2, \cdots, \mathcal O_k$，满足轨道内的每个元素的轨道等于该轨道。

轨道-稳定子定理

所有保持 $a$ 不动的变换 $G_a$ 复合任意一个把 $a$ 作用到 $b\in \mathcal O_a$ 的变换，均可得到所有把 $a$ 作用到 $b$ 的变换 $G_{a\to b}$，且这些变换两两不同，即 $|G_a| = |G_{a\to b}|$。

• 为什么两两不同：由消去律，若 $g_1x = g_2x$，则 $g_1 = g_2$。这说明 $|G_a| \leq |G_{a\to b}|$。
• 为什么是所有：把上述分析倒过来可得 $|G_{a\to b}| \leq |G_a|$。考虑 $G_{a\to b}$ 的每个变换复合某个 $g\in G_{b\to a}$，则得到两两不同且保持 $a$ 不变的变换，于是 $|G_{a\to b}|\leq |G_a|$。

$G$ 的每个变换将 $a$ 变成其轨道中的某个元素，所以每个元素都落在乘法表中，且恰好出现一次。

Burnside 引理

$$\sum_{a\in A} |G_a| = \sum_{a\in A} \sum_{g\in G} [g\cdot a = a] = \sum_{g\in G} \sum_{a\in A} [g\cdot a = a] = \sum_{g\in G} f(g).$$

$\square$

Burnside 引理的公式中有 $\frac 1 n$，但 $n$ 在模意义下可能没有逆元。解决方法有两个（本质相同）：

• 将每个数写成 $an + b$ 的形式进行计算，最后取出 $n$ 前面的系数，此时 $b$ 一定等于 $0$。注意 $b$ 不能对模数取模，且只有在算出整个和式之后才能忽略 $b$。
• 设模数为 $p$。考虑对 $n\times p$ 取模，这样算出来的结果一定是 $n$ 的倍数，除掉 $n$ 即可。更一般地，为保证 $n$ 在模意义下有逆元，根据逆元存在的充要条件，可以考虑对 $\gcd(n, p)\times p$ 取模。这是为了防止模数过大导致需要计算两个 __int128 大小的数相乘。

Pólya 计数定理

$g_i$ 表示向右循环移位 $i$ 个下标。这是一个排列，可以分解为若干个环，每个元素移动到出边指向的位置。如果 $a$ 在 $g_i$ 下不变，那么对于 $g_i$ 的每个环，都需要满足 $a$ 在环的所有位置上相等。因此，每个环有 $m$ 种方案，总方案数（不动点数量）为 $m ^ {c(g_i)}$，其中 $c(g)$ 表示排列 $g$ 的环的数量。根据经典的数论知识（见 同余代数 1.7 小节），$c(g_i) = \gcd(n, i)$。

由 Burnside 引理，只需证明 $f(g) = m ^ {c(g)}$。若一组染色方案在 $g$ 下是不动点，那么 $g$ 的每个环的所有元素的颜色相同。每个环有 $m$ 种染色方案，由乘法原理即得。$\square$

例题

P4980 【模板】Pólya 定理

P5233 [JSOI2012] 爱之项链

P3307 [SDOI2013] 项链

P1446 [HNOI2008] Cards

• “任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替” 保证给出的排列在复合下封闭。
• “对每种洗牌法，都存在一种洗牌法使得能回到原状态” 保证排列有逆排列。

P4128 [SHOI2006] 有色图

• 每次取出 $c_i$ 个数进行排列，方案数为 $\frac {n!} {(n - c_i)!}$，但每个不同的环会被算 $c_i$ 次，所以要除掉 $c_i$。这部分乘起来是 $\frac {n!} {\prod_{i = 1} ^ k c_i}$。
• 相同大小的环之间是无序的，但我们依次确定每个环导致相同大小的环之间有序，所以要除掉 $d_j!$。

P4727 [HNOI2009] 图的同构计数

P8633 [蓝桥杯 2015 国 B] 模型染色

*CF1630E Expected Components

根据经典数论结论（步长与子环，同余理论 1.7），旋转 $i$ 个下标的置换 $g_i$ 会将大小为 $n$ 的环分成 $d = \gcd (n, i)$ 个大小为 $\frac n d$ 的环。为了让序列在该变换下是不动点，每个环上的所有点的数字应当相同。例如当 $i = 2$，$n = 6$ 时，只有满足 $a_1 = a_3 = a_5$ 且 $a_2 = a_4 = a_6$ 的 $\{a_i\}$ 是变换的不动点。所以，固定 $a_{1\sim d}$ 即可确定整个序列。

如何做到线性

设 $k$ 表示 $\{a_i\}$ 有多少个不同的数。

因为 $L\leq \min_{j = 1} ^ n c_j \leq \frac n k$，所以最多有 $\frac n k$ 个合法的 $d$。而预处理阶乘和阶乘逆元后计算 $f_L$ 的复杂度为 $\mathcal{O}(k)$，所以可线性求出所有需要的 $f_L$，再乘以有多少个 $\gcd(i, n) = d$。这是经典结论，要求 $i$ 除以 $d$ 之后和 $\frac n d$ 互质，即 $\varphi(\frac n d)$，线性筛出欧拉函数即可。

P13227 [GCJ 2015 #2] Drum Decorator

• 如果一个位置填入 $4$，则所有相邻位置都要填入 $4$，导致所有位置都要填入 $4$。但上下边界的 $4$ 不合法。所以每个位置只会填入 $1, 2$ 或 $3$。
• 如果一个位置填入 $3$，考虑这个连通块的上边界，一定是水平的。如果相邻两列的上边界高度不同，则较高的位置只和最多两个 $3$ 连通，不合法。同理可证下边界是水平的。于是每个 $3$ 的连通块一定恰好占据两行。
• $2$ 的连通块会形成环状结构。

222222

222211
211222

221221
221221

2221
2121
2122

*SP422 TRANSP2 - Transposing is Even More Fun

*P4916 [MtOI2018] 魔力环

*P4708 画画

CHANGE LOG

• 2025.8.1：重构文章。
• 2025.9.5：加入例题 P13227。

参考资料

• Pólya enumeration theorem —— Wikipedia。
• 抽象代数学习笔记 —— Alex_Wei。

• 群论学习笔记 —— xtx1092515503。