OI 中的群论

· · 算法·理论

注：为便于理解，笔者对概念和结论进行了简化和不严谨概括。关于抽象代数之群论，见 抽象代数学习笔记，其中轨道-稳定子定理是结论 4.2。

什么是群

简单地说，群可以理解为一族描述操作的元素 \{g_1, g_2, \cdots, g_n\} 构成的集合 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 不写。

因为逆元存在且唯一，所以群是具有 消去律 的。即若 gh = g'h，则 g = g'。

群作用

“操作” 体现为 G 的每个元素可以作用在满足条件的集合 A 的每个元素上，依然得到 A 中的元素，称为 G 作用在 A 上。例如，A 是所有长度为 4 且值域为 [1, 3] 的整数序列，g_i 表示向右循环移位 i 个下标。设 a = (1, 2, 3, 3)，则 g_1a = (3, 1, 2, 3)。

群作用

映射 \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 一定是双射。

群其实是把 “变换“ 这个概念抽象成符号之后得到的具有一些基本性质的一族变换。一个变换的性质体现于它作用在集合上产生的效果，而群的性质体现于变换之间满足的特定关系。例如，在上例中，g_i = g_1 ^ i，g_0 = 1。

为什么要学习群

我们常说的 “群描述对称性” 是指一些常见的群可以由作用对象的对称性得出。例如，保持正方形及其定向不变（即不允许翻转）的群是四阶循环群 Z_4 = \{g_0, g_1, g_2, g_3\}，其中 g_k 表示沿中心顺时针旋转 \frac {k\pi} 2（如果允许翻转，则是八阶二面体群 D_8）。将正方形的四个角用任意排列标号，那么一个标号和它的循环移位所对应的正方形相等，我们认为这些正方形处于相同的 “等价类”，称为 轨道。

轨道 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，满足轨道内的每个元素的轨道等于该轨道。

所以，对称性的说法是先有等价类才有了群，群描述了等价类，也就是对象的对称性。

OI 中的群论问题一般是反过来的，形如 给定 G, A 和 G 在 A 上的群作用，求等价类（轨道）数量。例如，计算长为 n 且值域为 [1, m] 的整数序列的数量，其中序列循环同构，即如果 a 可以通过循环移位得到 b，则认为 a, b 相等。这里，G 是所有可能的循环移位，A 是所有长为 n 且值域为 [1, m] 的整数序列。两个序列在相同等价类当且仅当它们可以通过循环移位相互得到，因此等价类数量就是题目所求的答案。

轨道数量怎么求呢？

轨道-稳定子定理

考虑 G 作用在 A 上，每个 a\in A 有轨道 \mathcal O_a。设 G_a = \{g\mid g\cdot a = a\} 表示所有保持 a 不变的 G 的变换（称为 稳定子，稳定化子 stabilizer），则

|\mathcal O_a| |G_a| = |G|.

可以想象一个乘法表：G_a 的变换写在每列的上边，对每个 b\in \mathcal O_a 任选变换 g_b 使得 g_b\cdot a = b 写在每行的左边。每行每列的交点填入对应两个变换的复合（乘的顺序要一致，例如都是上边复合左边），则整个表恰好可以乘出 G 的所有变换。

所有保持 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|。

Burnside 引理

考虑 G 作用在 A 上，我们希望计算轨道的数量。对每个轨道 \mathcal O_i 和 a_i\in \mathcal O_i，根据轨道-稳定子定理，|\mathcal O_i||G_{a_i}| = |G|。又因为轨道内所有元素的稳定子数量相同（所有元素的轨道相等，用轨道-稳定子定理即可），所以

\sum_{a_i\in \mathcal O_i} |G_{a_i}| = |G|,

即一个轨道内所有元素的稳定子数量之和等于 |G|。

每个元素恰属于一个轨道，所以我们将所有元素的稳定子数量加起来，所得结果就是对每个轨道都求出其中所有元素的稳定子数量之和后再求和。因此，将结果除以 |G| 就是轨道数量 k。

k = \frac {1} {|G|}\sum_{a\in A} |G_a|.

但是一般而言 A 是很大的集合（例如，所有长为 n 且值域为 [1, m] 的整数序列），所以这个公式还不够好用。

我们换一种求和方式。本来是对每个元素求有多少个变换使得它不变，考虑转换视角，对每个变换求有多少元素在该变换下不变。对 g\in G，设 f(g) 表示使得 g\cdot a = a（不动点）的 a 的数量，则 \sum_{a\in A} G_a = \sum_{g\in G} f(g)。

\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 引理

k = \frac 1 {|G|}\sum_{g\in G} f(g).

如果序列只是循环同构，那么 G 的大小仅有 n，这使得 Burnside 引理比前一个公式好用了很多。

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 计数定理

Pólya 计数定理是 Burnside 引理的特例，这里只介绍简化版本。

依然考虑先前的例子，计算长为 n 且值域为 [1, m] 的整数序列在循环同构下的数量。此时 G = \{g_0, g_1, \cdots, g_{n - 1}\} 是所有长为 n 的循环移位。根据 Burnside 引理，计算 f(g_i)。

更一般地，对于给定置换群（即一些排列构成的群）$G$，如果认为两个能通过 $G$ 中的排列相互得到的序列是等价的，那么不同的序列数量为 $$ \frac 1 {|G|} \sum_{g\in G} m ^ {c(g)}. $$ 称为 **Pólya 计数定理**。 > 由 Burnside 引理，只需证明 $f(g) = m ^ {c(g)}$。若一组染色方案在 $g$ 下是不动点，那么 $g$ 的每个环的所有元素的颜色相同。每个环有 $m$ 种染色方案，由乘法原理即得。$\square

例题

P4980 【模板】Pólya 定理

Pólya 定理的简单应用。旋转 k 个下标的排列的环数为 \gcd(n, k)，所以答案为 \sum_{i = 0} ^ {n - 1} n ^ {\gcd(i, n) - 1}。

枚举 d\mid n，原式等于

\sum_{d\mid n} n ^ {d - 1} \sum_{i = 0} ^ {n - 1} [\gcd(i, n) = d] = \sum_{d\mid n} n ^ {d - 1} \varphi\left(\frac n d\right).

直接计算即可，时间复杂度 \mathcal{O}(Td(n)\sqrt n)。代码。

P5233 [JSOI2012] 爱之项链

问题的两部分是独立的。使用 Burnside 引理算出有多少种可能的戒指，再求出长度为 N 的环的相邻不同的染色方案数（颜色数量是戒指的数量）。这里，我们认为特殊纪念品在序列的第 N 个位置和第 1 个位置之间。就算两个不同的序列在循环移位下相等，它们也对应不同的项链，因为特殊纪念品的位置不同。

用 C 种颜色给长度为 N 的环染色，要求相邻不同，方案数为 (C - 1) ^ N + (-1) ^ N (C - 1)。这个是经典问题。

时间复杂度 \mathcal{O}(\sqrt M + \log N)。代码。

P3307 [SDOI2013] 项链

怎么这么多项链题，和 P5233 一样是二合一。

先算有多少种珠子 m，也就是

\sum_{1\leq i\leq j\leq k\leq a} [\gcd(i, j, k) = 1].

经典莫比乌斯反演，得到

\begin{aligned} m & = \sum_{d \mid a} \mu(d) \sum_{1\leq i\leq j\leq k\leq \frac a d} 1 \\ & = \sum_{d\mid a} \mu (d) \binom {\frac a d} 3. \end{aligned}

循环同构，考虑 Burnside 引理，计算旋转 i 下标之后相等的项链数量，要求项链在模 d = \gcd(n, i) 相同的下标上的珠子是相同的。题目还要求相邻不同，结合前一个限制，等价于仅考虑前 d 个位置构成的环时相邻不同。这部分和 P5233 一样，直接套公式

(m - 1) ^ n + (-1) ^ n(m - 1)

即可。注意 n 可能是 p 的倍数，所以我们使用之前提到的技巧，将答案写成 an + b 的形式，或对 p ^ 2 取模。

时间复杂度 \mathcal{O}(\sqrt n + a)。代码。

P1446 [HNOI2008] Cards

题意就差把 Burnside 引理写在脸上了：给定一个置换群，求所有可能的牌堆在该置换群的作用下形成的等价类数量。

使用 Burnside 引理，求每个排列的不动点数量。每个环上的颜色要相同，且每个颜色的数量需要满足题目限制。简单背包即可。

时间复杂度 \mathcal{O}(mS_rS_bS_g)。代码。

P4128 [SHOI2006] 有色图

因为图在排列下同构，所以答案是所有 m 种颜色的 n 元无向完全图在 n 元对称群（所有 n 阶排列构成的群）作用下的等价类数量。考虑 Burnside 引理。

对于每个排列 p，考虑 p 的不动点数量。

对于排列的每个环，(0, k) 和 (1, k + 1) 的颜色相同，以此类推。于是对每个 1\leq k\leq \frac c 2，所有距离为 k 的边的颜色相同，其中 c 是环长。环内部的 “自由度” 为 \lfloor \frac c 2 \rfloor。

对于环长分别为 c_1 和 c_2 的环之间的边，固定 k，对所有 i，(i\bmod c_1, (k + i) \bmod c_2) 的颜色相同。第一个位置每次回到 0，第二个位置会跳 c_1 步，所以总共形成 \gcd(c_1, c_2) 个子环，环之间的 “自由度” 为 \gcd(c_1, c_2)。

注意到我们只关心环长形成的集合，所以直接枚举 n 的所有分拆，算出对应的不动点数量以及排列数量，相乘后求和再除以 n! 即可。对于环长集合 c_1, \cdots, c_k，不动点数量已经给出。根据经典组合结论，排列数量为

\frac {n!} {\left(\prod_{i = 1} ^ k c_i\right)\left(\prod_{j = 1} ^ n d_j!\right)},

其中 d_j 表示长度为 j 的环的数量。

时间复杂度 \mathcal{O}(P(n) n ^ 2)，其中 P(n) 表示 n 的分拆数。代码。

P4727 [HNOI2009] 图的同构计数

是 P4128 的 m = 2，p = 997 版本。

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

变换是所有使得图同构的点置换，作用的集合是所有可能的染色。暴力枚举排列判定图同构，再使用 Burnside 引理即可。

时间复杂度 \mathcal{O}(n!n ^ 2)。代码。

*CF1630E Expected Components

问题要求价值的期望，即每个本质不同排列的连通块数量之和除以本质不同排列的数量。

Part I

先考虑本质不同排列的数量。因为序列循环同构，所以自然地想到 Burnside 引理。对每个 0\leq i < n，求出循环移位 i 个下标的不动点数量，也就是有多少个序列在该变换下是不变的。

根据经典数论结论（步长与子环，同余理论 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} 即可确定整个序列。

方案数是多少呢？设 L = \frac n d，也就是每个环的长度。因为环上的数相同，所以每个数的出现次数都应是 L 的倍数。设 c_j 表示 j 在给定的 \{a_i\} 当中的出现次数，则 L\mid c_j，否则无解。在此基础上，枚举每个数在哪些环，得到方案数

f_L = \binom d {\frac {c_1} L, \frac {c_2} L, \cdots, \frac {c_n} L}.

注意方案数 f_L 和 i 的值无关，只和 d 有关。

此外，d 还需满足 L\mid \gcd(c_1, \cdots, c_n)。这部分的时间复杂度为 \mathcal{O}(nd(n))。

如何做到线性

设 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)，线性筛出欧拉函数即可。

Part II

连通块数量等于有多少对相邻两个数不同。我们枚举每对相邻的位置，算出有多少个本质不同的排列在这个地方产生了贡献。注意这要求至少有两个环，那么相邻两个位置一定在不同的环。

直接枚举这两个数 x, y\ (x\neq y)，x 在前，y 在后，有 n 组相邻的位置可以填，填完之后对应的环就固定了。剩下的环依然是随便填，方案数为

\binom {d - 2} {\frac {c_1} L, \cdots, \frac {c_x} L - 1, \cdots, \frac {c_y} L - 1, \cdots, \frac {c_n} L} = \frac {f_d c_xc_y} {d(d - 1)L ^ 2}.

而

\sum_{x\neq y} c_xc_y = \left(\sum_{x = 1} ^ n c_x\right) ^ 2 - \sum_{x = 1} ^ n c_x ^ 2,

所以

g_d = \frac {nf_d} {d(d - 1)L ^ 2}\left(n ^ 2 - \sum_{j = 1} ^ n c_j ^ 2\right).

时间复杂度视实现精细程度为 \mathcal{O}(nd(n)) 或 \mathcal{O}(n)。

一份线性的 代码。

P13227 [GCJ 2015 #2] Drum Decorator

首先考虑刻画合法装饰方式。

通过打表找规律或简单分析可知：

用相邻的两个 1 覆盖一些位置（但不能和其它的 1 连通），使得剩下的位置形成若干个环。根据总度数的限制容易证明只有以下四种情况：

222222

222211
211222

221221
221221

2221
2121
2122

每若干行一定是以上元素的不断重复，不同的若干行之间由 3 连通块隔开。

题目要求循环同构，Burnside 引理 + DP 即可。因为 12 一定是一行的循环节，所以对于循环移位 i，我们只关心 \gcd(i, C, 12)。

时间复杂度 \mathcal{O}(n)。代码。

*SP422 TRANSP2 - Transposing is Even More Fun

对于 2 ^ a \times 2 ^ b 的矩阵，第 i 行第 j 列在内存中的下标为 i \times 2 ^ b + j。把每个位置的下标看成 a + b 位的二进制数，则转置相当于将这个数向右循环移位 b 位。

因为一个长为 c 的环需要 c - 1 次交换操作归位，所以答案为 2 ^ {a + b} 减去环的数量。后者是 a + b 位二进制数在循环移位 kb\ (0\leq k < \frac n {\gcd(n, b)}) 位构成的群的作用下形成的等价类数量。

使用 Burnside 引理，得到答案为

\frac {1} {\frac n g} \sum_{d\mid \frac n g} 2 ^ {\frac n d}\varphi(d).

其中 n = a + b。时间复杂度 \mathcal{O}(n\log n + Td(n))。代码。

*P4916 [MtOI2018] 魔力环

使用 Burnside 引理，求循环移位的不动点数量。问题转化为给定 L, m, k，求长度为 L 的环放 m 个 1 且不能有超过 k 个 1 相邻的方案数。

先考虑链的情况。这是经典问题，容斥，钦定 i 个 0 前面有连续 k + 1 个 1，总方案数为

\sum_{i \geq 0} (-1) ^ {i}\binom {L - i(k + 1)} {L - m} \binom {L - m + 1} i,

其中第二个组合数的上指标要加 1，是考虑到末尾有连续 k + 1 个 1 的情况。i 的上界为 \frac L k 级别。

对于环，枚举开头和结尾的 1 连续段的总长，有 k 种可能性。于是计算一组 L, m, k 的时间为 \mathcal{O}(L)。

因为 L\mid n，所以时间复杂度为 n 的约数和，即 \mathcal{O}(\sigma(n))。可以证明 \sigma(n) = \mathcal{O}(n\log \log n)。

*P4708 画画

好题。

编号无关，枚举所有环长可重集，要求每个点的度数都是偶数。

在环内部，两端距离为 k 的边要么同时出现，要么同时不出现。只有当 k = \frac c 2 时会改变所有点的奇偶性，其它时候均成环。

在环之间，一共有 d = \gcd(c_1, c_2) 组，每组让大小为 c_i 的环上每个点的度数增加 \frac {c_1c_2} {d c_i}，于是每组边会改变一个环或者两个环上所有点的奇偶性。

问题转化为：每个点可以被操作 d_i 次，每条边可以被操作 e_j 次（操作两个端点），求所有点被操作偶数次的方案数。根据整体的奇偶性要求，可知每个点被单独操作的次数之和为偶数。此时，对每个连通块（e_j > 0 的边形成的连通块），选择一棵生成树，不在生成树上的边随意，则树边有唯一方案使得满足条件。

因此，设连通块有 C 个点，D = \sum d_i，E = \sum e_j，则自由度为 \max(0, D - 1) + (E - (C - 1))。

时间复杂度 \mathcal{O}(P(n)n ^ 2)。代码。

CHANGE LOG

参考资料

全文

例题