专栏文章

群论

fflower1
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipjfe4i
此快照首次捕获于
2025/12/03 12:59
3 个月前
此快照最后确认于
2025/12/03 12:59
3 个月前
查看原文

群论

群

群的定义

若集合 S≠∅S\ne\varnothing 和集合 SS 上的运算 ⋅\cdot 构成的代数结构 (S,⋅)(S,\cdot) 满足以下性质:
1.封闭性：∀a,b∈S,a⋅b∈S\forall a,b \in S,a \cdot b \in S 。
2.结合律：∀a,b,c∈S,(a⋅b)⋅c=a⋅(b⋅c)\forall a,b,c \in S,(a \cdot b) \cdot c = a \cdot (b \cdot c) 。
3.单位元： ∃e∈S,∀a∈S,a⋅e=a\exist e \in S,\forall a \in S,a \cdot e = a 。
4.逆元：∀a∈S,∃b∈S,a⋅b=b⋅a=e\forall a \in S,\exist b \in S, a \cdot b = b \cdot a = e，称 bb 为 aa 的逆元，记为 a−1a^{-1} 。
则称 (S,⋅)(S,\cdot) 为一个群。

群的性质

1.一个群的单位元唯一。
证明：
假设存在两个单位元 e1,e2e_1,e_2 ,有 e1e2=e1=e2e_1e_2=e_1=e_2 。
2.若 a⋅x=e,x⋅b=ea \cdot x =e,x \cdot b = e ，有 a=ba=b 。
证明：
x⋅a=(x⋅a)⋅(x⋅b)=x⋅(a⋅x)⋅b=x⋅b=ex \cdot a = (x \cdot a) \cdot (x \cdot b) = x \cdot (a \cdot x) \cdot b = x \cdot b = e 。
3.一个群中 xx 的逆元唯一。
证明：
假设 xx 有两个逆元 a,ba,b ，有 a=a⋅x⋅b=ba = a \cdot x \cdot b = b 。
4.逆元有消去律存在。即 ∀ax=bx⇔a=b\forall ax = bx \Leftrightarrow a = b 。
证明：
方程两边同时乘逆元。

子群

子群：对于一个群 G(S,⋅)G(S,\cdot) ,若 T⊆ST \subseteq S ，且 H(T,⋅)H(T,\cdot) 也是一个群，那么称 HH 是 GG 的子群，记为 H≤G H \le G 。
生成子群：对于一个群 GG 的一个非空子集 TT ，如果 HH 是包含 TT 的 GG 的子群中最小的，则子群 HH 称为由子集 TT 生成的子群，记为⟨T⟩\left\langle T \right\rangle 。当 T={x}T = \left\{ x \right\}，也写作 ⟨x⟩\left\langle x \right\rangle 。
循环群：可由一个元素生成的群。

阶

群 GG 的阶等于它的元素个数，记作 ∣G∣|G|。
群 GG 中元素 xx 的阶等于最小的正整数 dd ，使得 xd=ex^d = e ，有限群中元素的阶一定存在 。

陪集

陪集：对于一个群 GG 的一个子群 HH 。
如果 H≤GH \le G ，对于 a∈Ga \in G ，定义 HH 的一个左陪集为 aH={ah∣h∈H}aH = \{ ah \mid h \in H \}，HH 的一个右陪集为 Ha={ha∣h∈H}Ha = \{ ha \mid h \in H \} 。

陪集的性质

若 H≤GH \le G ，有以下性质。
1.∀a∈G\forall a \in G ，有 ∣H∣=∣Ha∣| H | = | Ha | 。
证明：
若h1,h2∈H,h1≠h2 h_1,h_2 \in H,h_1 \ne h_2，则h1a≠h2ah_1a \ne h_2a 。即对于不同的 hh ，haha 互不相同 。
2.∀a∈G\forall a \in G ，有 a∈Haa \in Ha 。
证明：
因为 HH 是群，所以 e∈He \in H ，所以 ea∈Haea \in Ha 即 a∈Haa \in Ha 。
3.Ha=H⇔a∈HHa = H \Leftrightarrow a \in H 。
证明：
从左往右，由性质2得 a∈Haa \in Ha ，可得 a∈Ha \in H 。
从右往左，由群的封闭性得 Ha⊆HHa \subseteq H，又因为 ∣H∣=∣Ha∣| H | = | Ha | ，可得 Ha=HHa = H 。
4.Ha=Hb⇔ab−1∈HHa = Hb \Leftrightarrow ab^{-1} \in H 。
证明：
从左往右，可得 Hab−1=HHab^{-1} = H，根据性质3有 ab−1∈Hab^{-1} \in H 。
从右往左，根据性质三有 Hab−1=HHab^{-1} = H，可得 Ha=HbHa = Hb 。
5.若 Ha∩Hb≠∅Ha \cap Hb \ne \varnothing，有 Ha=HbHa = Hb 。
证明：若 Ha∩Hb≠∅Ha \cap Hb \ne \varnothing ，有 ∃h1,h2∈H,h1⋅a=h2⋅b\exist h_1 , h_2 \in H , h_1 \cdot a = h_2 \cdot b ，可得 a⋅b−1=h2⋅h1−1a \cdot b^{-1} = h_2 \cdot h_1^{-1}，又因为 h2⋅h1−1∈Hh_2 \cdot h_1^{-1} \in H ，所以 a⋅b−1∈Ha \cdot b^{-1} \in H ，根据性质4有 Ha=HbHa = Hb 。
6.HH 的所有右陪集的并集为 GG 。 由于封闭性，不可能取到 GG 之外的元素。 由于 e∈He \in H ，取遍 GG 的所有元素就可以保证 GG 的所有元素都被取到。

拉格朗日定理

若 H≤GH \le G，那么 ∣G∣=∣H∣[G:H]| G | = | H | [G : H] 。
其中 [G:H][G : H] 表示 GG 中 HH 不同陪集的数量。
证明：
HH 的所有陪集大小相等且互不相交。
群 GG 中元素 xx 的阶整除群 GG 的阶。
证明：构造一个 GG 的子群 H={e,x,x2,…,xd−1}H = \{ e,x,x^2,\dots,x^{d-1} \} , 由拉格朗日定理可得 dd 整除 ∣G∣| G | 。

置换

置换的定义

有限集合到自身的双射)称为置换。不可重集合 S={1,2,…,n}S = \{1,2,\dots,n\} 上的置换可以表示为 (1,2,3,…，na1,a2,a3,…,an)\begin{pmatrix} 1,2,3,\dots，n\\a_1,a_2,a_3,\dots,a_n\end{pmatrix} ，可省略表示为 (a1,a2,a3,…,an)(a_1,a_2,a_3,\dots,a_n)，表示把第 aia_i 个元素映射到位置 ii 。
置换 ff 作用于状态 aa ，写作 f⋅af \cdot a 。

置换的乘法

定义 f1⋅f2f_1 \cdot f_2 表示先进行 f2f_2 ，再进行 f1f_1 。
(a1,a2,…,an)⋅(b1,b2,…,bn)=(ba1,ba2,…,ban)(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})

循环

如果一个置换形如 (a2,a3,…,an,a1)(a_2,a_3,\dots,a_n,a_1) ，则称其为一个循环。
如果两个循环不包含相同元素，则称它们是不相交的。
任何置换都可以分解为若干个不相交循环的置换的乘积。

置换群

元素个数为 nn 的所有排列的集合 NN 与置换乘法组成的一个群 (N,⋅)(N,\cdot) 。
其子群称为置换群。
其中的单位元又叫做恒等置换 II 。

等价类

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

不动点

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

轨道-稳定子定理

置换群 GG 和集合 XX ，对于每个 x∈Xx \in X 。
定义 G(x)={g⋅x,g∈G}G(x) = \{ g \cdot x,g \in G\} 为 xx 的轨道。
Gx={g∣g⋅x=x,g∈G}G^x = \{g \mid g \cdot x = x , g \in G\} 为 xx 的稳定子。
轨道-稳定子定理：∣G∣=∣Gx∣∣G(x)∣| G | = | G^x | | G(x) |
证明：
首先，GxG^x 是 GG 的一个子群。
1.封闭性：因为 f⋅x=x,g⋅x=xf \cdot x = x,g \cdot x = x ，有 (f⋅g)⋅x=x(f \cdot g) \cdot x = x ，即 f⋅g∈Gxf \cdot g \in G^x 。
2.结合律：置换乘法本身始终有结合律。
3.单位元： e⋅x=xe \cdot x = x 。
4.逆元： f−1⋅x=f−1⋅(f⋅x)=(f−1⋅f)⋅x=e⋅x=xf^{-1} \cdot x = f^{-1} \cdot (f \cdot x) = (f^{-1} \cdot f) \cdot x = e \cdot x = x ，所以 f−1∈Gxf^{-1} \in G^x 。
根据拉格朗日定理，有: ∣G∣=∣Gx∣∣G:Gx∣| G | = | G^x | | G : G^x | 。
其中 ∣G:Gx∣| G : G^x | 表示 GxG^x 在 GG 中本质不同的陪集数量。
那么现在只需要证明 ∣G:Gx∣=∣G(x)∣| G : G^x | = | G(x) | ，尝试在 GxG^x 的陪集和 G(x)G(x) 间建立双射关系。
1.若 f⋅x=g⋅xf \cdot x =g \cdot x ，则有 (g−1⋅f)⋅x=x(g^{-1} \cdot f) \cdot x = x ，即 g−1⋅f∈Gxg^{-1} \cdot f \in G^x ，由陪集的性质四，可得 fGx=gGxfG^x = gG^x ，即轨道相同则陪集相同。
2.若 fGx=gGxfG^x = gG^x ，则 g−1⋅f∈Gxg^{-1} \cdot f \in G^x , 所以 g−1⋅f⋅x=xg^{-1} \cdot f \cdot x = x ，即 f⋅x=g⋅xf \cdot x =g \cdot x ，即陪集相同则轨道相同。
所以成功建立起了双射关系，命题得证。

Burnside引理

对于作用于集合 XX 的群 GG 。定义 X/GX / G 为 XX 在 GG 的作用下等价类的集合。
Burnside 引理： ∣X/G∣=1∣G∣∑g∈G∣Xg∣| X / G | = \dfrac{1}{| G |} \displaystyle\sum\limits_{g \in G}| X^g |
其中 Xg={x∣g⋅x=x,x∈X}X^g = \{ x \mid g \cdot x = x,x \in X\} ，即集合 XX 在 gg 作用下的不动点数量。
证明：
| 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) |$ ，所以 $$\begin{aligned} | 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)}$ 。 使用莫比乌斯反演化简原式。 $$\begin{aligned} 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
$|G| = n!$，里外两项抵消，得到最终公式：
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)$。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...