群论

· · 算法·理论

群论

群

群的定义

若集合 S\ne\varnothing 和集合 S 上的运算 \cdot 构成的代数结构 (S,\cdot) 满足以下性质:

1.封闭性：\forall a,b \in S,a \cdot b \in S 。

2.结合律：\forall a,b,c \in S,(a \cdot b) \cdot c = a \cdot (b \cdot c) 。

3.单位元： \exist e \in S,\forall a \in S,a \cdot e = a 。

4.逆元：\forall a \in S,\exist b \in S, a \cdot b = b \cdot a = e，称 b 为 a 的逆元，记为 a^{-1} 。

则称 (S,\cdot) 为一个群。

群的性质

1.一个群的单位元唯一。
证明：
假设存在两个单位元 e_1,e_2 ,有 e_1e_2=e_1=e_2 。

2.若 a \cdot x =e,x \cdot b = e ，有 a=b 。
证明：

3.一个群中 $x$ 的逆元唯一。 证明： 假设 $x$ 有两个逆元 $a,b$ ，有 $a = a \cdot x \cdot b = b$ 。 4.逆元有消去律存在。即 $\forall ax = bx \Leftrightarrow a = b$ 。 证明： 方程两边同时乘逆元。 #### 子群 子群：对于一个群 $G(S,\cdot)$ ,若 $T \subseteq S$ ，且 $H(T,\cdot)$ 也是一个群，那么称 $H$ 是 $G$ 的子群，记为 $ H \le G$ 。 生成子群：对于一个群 $G$ 的一个非空子集 $T$ ，如果 $H$ 是包含 $T$ 的 $G$ 的子群中最小的，则子群 $H$ 称为由子集 $T$ 生成的子群，记为$\left\langle T \right\rangle $。当 $T = \left\{ x \right\}$，也写作 $\left\langle x \right\rangle$ 。 循环群：可由一个元素生成的群。 #### 阶 群 $G$ 的阶等于它的元素个数，记作 $|G|$。 群 $G$ 中元素 $x$ 的阶等于最小的正整数 $d$ ，使得 $x^d = e$ ，有限群中元素的阶一定存在 。 #### 陪集 陪集：对于一个群 $G$ 的一个子群 $H$ 。 如果 $H \le G$ ，对于 $a \in G$ ，定义 $H$ 的一个左陪集为 $aH = \{ ah \mid h \in H \}$，$H$ 的一个右陪集为 $Ha = \{ ha \mid h \in H \}$ 。 #### 陪集的性质 若 $H \le G$ ，有以下性质。 1.$\forall a \in G$ ，有 $| H | = | Ha |$ 。 证明： 若$ h_1,h_2 \in H,h_1 \ne h_2$，则$h_1a \ne h_2a$ 。即对于不同的 $h$ ，$ha$ 互不相同 。 2.$\forall a \in G$ ，有 $a \in Ha $ 。 证明： 因为 $H$ 是群，所以 $e \in H$ ，所以 $ea \in Ha$ 即 $a \in Ha$ 。 3.$Ha = H \Leftrightarrow a \in H$ 。 证明： 从左往右，由性质2得 $a \in Ha$ ，可得 $a \in H$ 。 从右往左，由群的封闭性得 $Ha \subseteq H$，又因为 $| H | = | Ha |$ ，可得 $Ha = H$ 。 4.$Ha = Hb \Leftrightarrow ab^{-1} \in H$ 。 证明： 从左往右，可得 $Hab^{-1} = H$，根据性质3有 $ab^{-1} \in H$ 。 从右往左，根据性质三有 $Hab^{-1} = H$，可得 $Ha = Hb$ 。 5.若 $Ha \cap Hb \ne \varnothing$，有 $Ha = Hb$ 。 证明：若 $Ha \cap Hb \ne \varnothing$ ，有 $\exist h_1 , h_2 \in H , h_1 \cdot a = h_2 \cdot b$ ，可得 $a \cdot b^{-1} = h_2 \cdot h_1^{-1}$，又因为 $h_2 \cdot h_1^{-1} \in H$ ，所以 $a \cdot b^{-1} \in H$ ，根据性质4有 $Ha = Hb$ 。 6.$H$ 的所有右陪集的并集为 $G$ 。 由于封闭性，不可能取到 $G$ 之外的元素。 由于 $e \in H$ ，取遍 $G$ 的所有元素就可以保证 $G$ 的所有元素都被取到。 #### 拉格朗日定理 若 $H \le G$，那么 $| G | = | H | [G : H]$ 。 其中 $[G : H]$ 表示 $G$ 中 $H$ 不同陪集的数量。 证明： $H$ 的所有陪集大小相等且互不相交。 群 $G$ 中元素 $x$ 的阶整除群 $G$ 的阶。 证明：构造一个 $G$ 的子群 $H = \{ e,x,x^2,\dots,x^{d-1} \}$ , 由拉格朗日定理可得 $d$ 整除 $| G |$ 。 ## 置换 #### 置换的定义 有限集合到自身的双射)称为置换。不可重集合 $S = \{1,2,\dots,n\}$ 上的置换可以表示为 $\begin{pmatrix} 1,2,3,\dots，n\\a_1,a_2,a_3,\dots,a_n\end{pmatrix}$ ，可省略表示为 $(a_1,a_2,a_3,\dots,a_n)$，表示把第 $a_i$ 个元素映射到位置 $i$ 。 置换 $f$ 作用于状态 $a$ ，写作 $f \cdot a$ 。 #### 置换的乘法 定义 $f_1 \cdot f_2$ 表示先进行 $f_2$ ，再进行 $f_1$ 。 $(a_1,a_2,\dots,a_n) \cdot (b_1,b_2,\dots,b_n) = (b_{a_1},b_{a_2},\dots,b_{a_n})

循环

如果一个置换形如 (a_2,a_3,\dots,a_n,a_1) ，则称其为一个循环。

如果两个循环不包含相同元素，则称它们是不相交的。

任何置换都可以分解为若干个不相交循环的置换的乘积。

置换群

元素个数为 n 的所有排列的集合 N 与置换乘法组成的一个群 (N,\cdot) 。

其子群称为置换群。

其中的单位元又叫做恒等置换 I 。

等价类

若一个状态可以通过置换群内的某个置换到达另一个状态，则称它们是同一个等价类，即本质相同。

不动点

若 f \cdot x = x ，则称 x 为 f 的一个不动点。

轨道-稳定子定理

置换群 G 和集合 X ，对于每个 x \in X 。
定义 G(x) = \{ g \cdot x,g \in G\} 为 x 的轨道。

轨道-稳定子定理：$| G | = | G^x | | G(x) |

证明：

首先，G^x 是 G 的一个子群。

1.封闭性：因为 f \cdot x = x,g \cdot x = x ，有 (f \cdot g) \cdot x = x ，即 f \cdot g \in G^x 。

2.结合律：置换乘法本身始终有结合律。

3.单位元： e \cdot x = x 。

4.逆元： f^{-1} \cdot x = f^{-1} \cdot (f \cdot x) = (f^{-1} \cdot f) \cdot x = e \cdot x = x ，所以 f^{-1} \in G^x 。

根据拉格朗日定理，有: | G | = | G^x | | G : G^x | 。

其中 | G : G^x | 表示 G^x 在 G 中本质不同的陪集数量。

那么现在只需要证明 | G : G^x | = | G(x) | ，尝试在 G^x 的陪集和 G(x) 间建立双射关系。

1.若 f \cdot x =g \cdot x ，则有 (g^{-1} \cdot f) \cdot x = x ，即 g^{-1} \cdot f \in G^x ，由陪集的性质四，可得 fG^x = gG^x ，即轨道相同则陪集相同。

2.若 fG^x = gG^x ，则 g^{-1} \cdot f \in G^x , 所以 g^{-1} \cdot f \cdot x = x ，即 f \cdot x =g \cdot x ，即陪集相同则轨道相同。

所以成功建立起了双射关系，命题得证。

Burnside引理

对于作用于集合 X 的群 G 。定义 X / G 为 X 在 G 的作用下等价类的集合。

Burnside 引理： | X / G | = \dfrac{1}{| G |} \displaystyle\sum\limits_{g \in G}| X^g |

其中 X^g = \{ x \mid g \cdot x = x,x \in X\} ，即集合 X 在 g 作用下的不动点数量。

证明：

| X / G | &= \sum\limits_{Y \in X / G} 1\\ &=\sum\limits_{Y \in X / G} \sum\limits_{x \in Y} \dfrac{1}{| Y |}\\ &=\sum\limits_{Y \in X / G} \sum\limits_{x \in Y} \dfrac{1}{| G(x) |}\\ &=\sum\limits_{x \in X}\dfrac{1}{|G(x)|} \end{aligned}

根据轨道-稳定子定理，有 | G | = | G^x | | G(x) | ，所以

| X / G | &= \sum\limits_{x \in X}\dfrac{G^x}{|G|}\\ &= \dfrac{1}{|G|}\sum\limits_{x \in X}|G^x|\\ &=\dfrac{1}{| G |} \displaystyle\sum\limits_{g \in G}| X^g | \\ \end{aligned}

得证。

Polya定理

Polya 定理可以解决一般的染色计数问题。

Polya 定理： | X / G | = \dfrac{1}{| G |} \displaystyle\sum\limits_{g \in G}m^{c(g)}

其中 c(g) 表示置换 g 拆出的不相交循环数量，m 表示颜色数量。

证明：在 Burnside 引理中， g 的不动点满足 g 拆出的每个循环内的元素都相同，所以 |X^g| = m^{c(g)} 。

例题

P4980 【模板】Pólya 定理

定义 g_i 为置换：旋转 i 个点。

则答案即为环的所有不同颜色状态 X ，在群 G = \{g_0,g_1,\dots\,g_{n-1}\} 作用下的等价类数量。

由 Burnside 引理得到： ans = \dfrac{1}{n} \displaystyle\sum\limits_{i=1}^n | X^{g_i} | 。

考虑置换 g_i 作用于状态 X 的不动点数量，可以将其拆成 \gcd(i,n) 个不相交的循环，对于每个不动点，显然每个不相交的循环内颜色都相同，所以 |X^{g_i}| = n^{\gcd(i,n)} 。

使用莫比乌斯反演化简原式。

ans &= \dfrac{1}{n} \sum\limits_{i=1}^n n^{\gcd(i,n)} \\ &= \dfrac{1}{n} \sum\limits_{i=1}^n \sum\limits_{d=1}^n n^d [\gcd(i,n)==d] \\ &= \dfrac{1}{n} \sum\limits_{d|n} n^d \sum\limits_{i=1}^n [\gcd(i,n)==d] \\ &= \dfrac{1}{n} \sum\limits_{d|n} n^d \sum\limits_{i=1}^{\frac{n}{d}} [\gcd(i,\frac{n}{d})==1] \\ &= \dfrac{1}{n} \sum\limits_{d|n} n^d \varphi(\frac{n}{d}) \\ \end{aligned}

暴力计算欧拉函数时间复杂度 O(Td(n)\sqrt(n))。但可以对 n 进行质因数分解，在枚举质因数的时候O(1)计算\varphi，时间复杂度 O(T\sqrt{n})。

P1446 [HNOI2008] Cards

由于题目保证多次洗牌可以被单次洗牌代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。这个条件等价于给出的 m 个洗牌法构成的置换集合可以涵盖所有洗牌法，且满足逆元。

我们在 m 种洗牌法的基础上加入单位置换，就构成了置换群 G，可以使用 Burnside 引理求解。

由于数据范围较小，可以 dp 计算出每种洗牌方式作用于 X 的不动点个数，即可得出答案，时间复杂度 O(nm^4) 。

P4727 [HNOI2009] 图的同构计数

将图的顶点重新标号等价于对点集置换，所有标号方式构成了置换群 G，可以使用 Burnside 引理求解。

考虑求解 g 作用于 X 的不动点个数，对于 g 的不动点，观察发现有些边要么同时存在，要么同时不存在，我们称这些边为一个等价类。

设 k 为置换 g 作用下边的等价类个数，那么 X 中就有 2^k 个不动点，即 |X^g|=2^k 。

接下来要求置换 g 作用下边的等价类个数，首先将 g 拆成若个个不相交的置换循环，长度分别为 b_1,b_2,……,b_m 。

对于同一循环内的边，设循环长度为 b ，不难发现两条边是等价类当且仅当它们长度相同，长度为 b 的循环贡献为 \lfloor\frac{b}{2}\rfloor ，这一类边总的贡献为 \sum\limits_{i=1}^m \left\lfloor\frac{b_i}{2} \right\rfloor 。

对于连接两个循环的边，设这两个循环的长度分别为 b_1,b_2 ，那么每条边经过 \operatorname{lcm}(b_1,b_2) 次置换后会回归原位，所以每个等价类大小为 \operatorname{lcm}(b_1,b_2) ，总的等价类个数为 \frac{b_1b_2}{\operatorname{lcm}(b_1,b_2) )} = \gcd(b_1,b_2) ，总的贡献为 \sum\limits_{i=1}^m \sum\limits_{j=1}^{i-1} \gcd(b_i,b_j)。

所以边的等价类个数就等于两种情况之和：

k=\sum\limits_{i=1}^m \left\lfloor \frac{b_i}{2} \right\rfloor + \sum\limits_{i=1}^m \sum\limits_{j=1}^{i-1} \gcd(b_i,b_j) \\

由于 |G| = n ! ，因此不能枚举每一个置换 g ，需要进行优化。

观察到有许多置换会被重复计算，如果两个置换 b 的集合是相同的，其所产生的贡献也是相等，于是可以枚举 b 的不同集合，即 n 的分拆数代表一类置换。

现在需要计算对于每个拆分，对应置换的数量。首先将 n 个数分为 m 组，第 i 组有 b_i 个数，一共有 \frac{n!}{\prod (b_i!)} 种方案。

接着是循环内部数的分配，其需要构成一个循环，总共有 \prod (b_i-1)! 种方案。

注意到，对于长度相等的循环，它们之间互相交换的话会出现重复计数，设 c_i 表示置换 g 中长度为 i 的循环个数，答案会多算 c_i! 倍，因此答案还要除以 \prod (c_i!) 。

所以我们的到拆分 b 所对应的置换个数为：

\frac{n!}{\prod(b_i)\prod(c_i!)}

用枚举 b 改进之前枚举 g 的算法，可以得到：

|X/G| =\frac{1}{|G|} \sum\limits_{b} \frac{n!}{\prod(b_i)\prod{(c_i!)}}2^k $$ ans=\sum\limits_{b} \frac{2^k}{\prod(b_i)\prod{(c_i!)}} $$ $$ k=\sum\limits_{i=1}^m \left\lfloor \frac{b_i}{2} \right\rfloor + \sum\limits_{i=1}^m \sum\limits_{j=1}^{i-1} \gcd(b_i,b_j) \\ $$ 时间复杂度可以通过本题。 #### 扩展： P4128 [SHOI2006] 有色图 问题本质与上一题相同，条件改为对于边的等价类，每条边的颜色都一定相同，将 $2^k$ 改为颜色数 $c^k$ 即可。 ### P4916 [MtOI2018] 魔力环 本题可以使用 Burnside 引理，定义 $f(x)$ 为拆分出 $x$ 个不相交循环的不动点数量，对于旋转 $i$ 个，可以将其拆分称 $\gcd(i,n)$ 个不相交的循环。 $$\begin{aligned} ans&=\dfrac{1}{| n |} \sum\limits_{i=1}^n f(\gcd(i,n)) \\ &=\dfrac{1}{| n |} \sum\limits_{d|n}\sum\limits_{i=1}^n f(d) [\gcd(i,n)==d] \\ &=\dfrac{1}{| n |} \sum\limits_{d|n} f(d) \sum\limits_{i=1}^{\frac{n}{d}} [\gcd(i,\frac{n}{d})==1] \\ &=\dfrac{1}{| n |} \sum\limits_{d|n} f(d) \varphi(\frac{n}{d}) \\ \end{aligned}$$ 考虑求解 $f(x)$ ，其中 $m=n$ 的情况特判，其余情况循环节间互不影响，可以对 $\frac{n}{x}$ 个循环节单独考虑。 设 $g(n,m)$ 为用 $m$ 个黑球和 $n-m$ 个白球组成长度为 $n$ 的环，且黑球连续段长度不超过 $k$ 的方案数。 $$f(x)=\left[\frac{n}{x} \mid m\right] g\left(x,\frac{m}{\frac{n}{x}}\right)$$ 考虑如何求 $g(n,m)$ ，若 $m \le k$ ，则直接返回 $\tbinom{n}{m}$。 否则可以转化为用 $n-m$ 个白球将 $m$ 个黑球分为 $n-m+1$ 组（每组可以为空），且黑球数量不超过 $k$ 个。由于环的性质，还要求第一组和最后一组加起来不超过 $k$ 个，可以枚举第一组和最后一组共放的黑球数量。 $$g(n,m)=\sum\limits_{i=0}^{k} (i+1)s(n-m-1,m-i)$$ 其中 $s(n,m)$ 为将 $m$ 个黑球分为 $n$ 组，每组黑球数量不超过 $k$ 个，可以容斥计算： $$s(n,m)=\sum\limits_{i=0}^{\min(n,\lfloor\frac{m}{k+1}\rfloor)} (-1)^i\tbinom{n}{i}p(n,m-i(k+1))$$ 其中 $p(n,m)$ 为将 $m$ 个黑球分为 $n$ 组的方案数，可以组合数学插板法直接计算： $$p(n,m)=\tbinom{m+n-1}{n-1}$$ 时间复杂度为 $O(n+m \log m)$ 。 ### P3307 [SDOI2013] 项链 本题首先考虑求解本质不同的珠子数量 $c$ ，可以使用 Burnside 引理解决，分别计算每个置换的不动点方案数。定义 $T(x)$ 为不考虑旋转翻转同构， $x$ 个数最大公约数为 $1$ 的方案。 不动点：$3$ 个数可以任意取，贡献 $T(3)$。 旋转：两种旋转，需要 $3$ 个数相同，贡献 $2 \times T(1)$。 翻转：三种翻转，需要 $2$ 个数相同，贡献 $3 \times T(2) $。 总珠子数量 $c=\frac{T(3) + 3 \times T(2) + 2 \times T(1)}{6}$，其中 $T(1)=1$，尝试计算 $T(3)$。 $$\begin{aligned} T(3)&=\sum\limits_{i=1}^a \sum\limits_{j=1}^a \sum\limits_{k=1}^a [gcd(i,j,k)==1] \\ &=\sum\limits_{i=1}^a \sum\limits_{j=1}^a \sum\limits_{k=1}^a \sum\limits_{d|gcd(i,j,k)} \mu(d) \\ &=\sum\limits_{d=1}^a \mu(d) \sum\limits_{i=1}^a \sum\limits_{j=1}^a \sum\limits_{k=1}^a [d|i][d|j][d|k] \\ &=\sum\limits_{d=1}^a \mu(d) \left\lfloor \frac{a}{d} \right\rfloor^3 \\ \end{aligned}$$ 线性筛预处理后可以使用数论分块在 $O(\sqrt{a})$ 的时间内求解，$T(2)$ 可同理计算。 至此我们成功求出了本质不同的珠子数量，接下来考虑求出本质不同的项链数量，使用 Burnside 引理求解，定义 $f(n)$ 为拆分出 $n$ 个不相交循环的不动点数量。 $$\begin{aligned} ans &= \dfrac{1}{n} \sum\limits_{i=1}^n f(gcd(i,n)) \\ &= \dfrac{1}{n} \sum\limits_{d|n} f(d) \sum\limits_{i=1}^n [gcd(i,n)=d] \\ &= \dfrac{1}{n} \sum\limits_{d|n} f(d) \sum\limits_{i=1}^{\frac{n}{d}} [gcd(i,\frac{n}{d})=1] \\ &= \dfrac{1}{n} \sum\limits_{d|n} f(d) \varphi(\frac{n}{d}) \end{aligned}$$ 注意到每个循环节都相同，可以对循环节单独考虑，则 $f(n)$ 即为长度为 $n$ 的项链的合法方案数。 合法方案要求相邻两个珠子颜色不同，且首尾颜色不同，考虑递推求解 $f(n)$ ，若 $n-1$ 与第一个珠子颜色不同，贡献 $f(n-1) \times (c-2)$ ，若 $n-1$ 与第一个珠子颜色相同，贡献 $f(n-2) \times (c-1)$ ，得到递推式： $$f(n)=f(n-1) \times (c-2)+f(n-2) \times (c-1)$$ 此时使用矩阵快速幂即可做到 $O(\log n)$ ，但常数过大无法通过，于是尝试使用方程特征法求出通项公式。 $$r^2-r(c-2)-(c-1)=0$$ 解方程得到根 $r_1=c-1,r_2=-1$ ，得到递推关系通解。 $$f(n)=A(c-1)^n+B(-1)^n$$ 带入 $f(1)=0$ ，$f(2)=c(c-1)$ ，解得 $A=1,B=c-1$，得到通项公式。 $$f(n)=(c-1)^n+(c-1)(-1)^n$$ 最后枚举质因数 $O(1)$ 求欧拉函数即可解决本题，注意到 $n$ 可能整除 $10^9+7$ ，因此当 $n$ 是 $10^9+7$ 的倍数时，将模数改为 $(10^9+7)^2$ ，最后除 $10^9+7$ 即可。 时间复杂度 $O(Td(n)\log n)$。