群论
基本
代数系统：非空集 \(G\) 以及一堆二元运算组成一个代数系统，表示为 \((G,\cdots,\cdots)\)，其中后面表示每个运算的符号。
群：代数系统 \((G,\cdot)\)（称作乘法），满足以下性质则称为群（群公理）：
- 封闭性：对于任意 \(a,b(a,b\in G)\)，有 \(a\cdot b\in G\)。
- 结合律：对于任意 \(a,b,c(a,b,c\in G)\)，有 \((a\cdot b)\cdot c=a(b\cdot c)\)。
- 存在幺元：存在单位 \(e\in G\)，使得对于任意 \(a\in G\)，有 \(e\cdot a=a\cdot e=a\)，\(e\) 被称作单位元（幺元）。
- 存在逆元：对于任意 \(a\in G\)，都存在一个 \(b\) 使得 \(a\cdot b=b\cdot a=e\)，则 \(b=a^{-1}\)，\(b\) 是 \(a\) 的逆元。
有限群/无限群：有有限/无限个元素的群，定义一个有限群的阶为 \(G\) 的大小，记作 \(|G|\)。
交换群：带交换律的（对于任意 \(a,b(a,b\in G)\)，有 \(a\cdot b = b \cdot a\)）。
半群：若 \((G,\cdot)\) 满足封闭性和结合律，则称其为半群。
交换半群：带交换律的半群。
幺半群：存在单位元的半群。
子群：顾名思义，若两个群 \((G,\cdot),(H,\cdot)\)，满足 \(H\subseteq G\)，那么 \(H\) 为 \(G\) 的一个子群。
生成子群：若 \((G,\cdot)\) 的一个子集 \(S\)，满足 \((G,\cdot)\) 所有包含 \(S\) 的子群的交 \(H\) 还是群，那么称 \(H\) 为 \(S\) 的生成子群，可以记作 \(⟨S⟩\)，\(S\) 为 \(⟨S⟩\) 的生成集 。
环：代数系统 \((G,+,\cdot)\)（称作乘法、加法），满足以下性质则称为环：
-
\((G,+)\) 是一个交换群（环的加法群）。
-
\((G,\cdot)\) 是一个半群（环的乘法半群）。
-
\(\cdot\) 关于 \(+\) 有分配律：对于任意 \(a,b,c\in G\)，有 \(a\cdot(b+c)=a\cdot b+a\cdot c\)。
-
存在零元：零元即为 \((G,+)\) 的幺元。
交换环：带交换律的环。
幺环：若 \((G,\cdot)\) 是幺半群，那么， \((G,+,\cdot)\)为幺环，\((G,+,\cdot)\) 幺元为 \((G,\cdot)\) 的幺元。
陪集：若 \((H,\cdot)\) 是群 \((G,\cdot)\) 的一个子群，并且 \(a\in G\)，称 \(aH=\{a\cdot h | h\in H\}\) 为 \(H\) 的左陪集，\(Ha=\{h\cdot a | h\in H\}\) 为 \(H\) 的右陪集。
与陪集相关的一些性质（只考虑左陪集，右陪集类似）：
-
\(|H|=|aH|\)
-
\(aH=H\Leftrightarrow a\in H\)
-
\(aH=H\Rightarrow a\in H\) ：因为单位元，所以 \(a\in aH\) 所以 \(a\in H\)。
-
\(a\in H\Rightarrow aH=H\)：根据封闭性，\(aH\) 中所有元素在 \(H\) 中出现，又因为 性质 \(1\)： \(|H|=|aH|\) ，所以 \(aH=H\)。
-
-
\(aH=bH\Leftrightarrow a\cdot b^{-1}\in H\)
- 把 \(aH=bH\) 转化为 \(a\cdot b^{-1} H=H\)。
-
\(aH\cap bH\neq \varnothing \Rightarrow aH=bH\)
- 设 \(c\in aH\cap bH\)，于是 \(\exists\;t,u\in H,a\cdot t=b\cdot u=c\)，所以 \(a\cdot b^{-1}=u\cdot t^{-1}\in H\)。
商群：对于群 \((G,\cdot)\) 及其正规子群 \((H,\cdot)\) ，商群 \(G/H=\{gH|g\in G\}\)。
拉格朗日定理：\(|H|[G:H]=|G|\) （\([G:H]\) 为 \(G\) 中 \(H\) 不同的左陪集数量，即 \(|G/H|\)）。
- 根据陪集性质 \(4\)：本质不同陪集必定无交。
共轭：对于 \(g,a,b\in G\) ，有 \(b=g\cdot a\cdot g^{-1}\)，那么 \(a,b\) 共轭。
阶：群 \((G,\cdot)\) 中 \(a(a\in G)\) 的阶，是最小的正整数 \(k\) 使得 $a^k=e $ 。对于有限群阶一定存在。
与阶相关的性质：
- 群中任意一个元素的阶，一定整除群的阶。
- 若 \(a,b\in G\)，\(a,b\) 的阶分别为 \(u,v\) ，且 \(\gcd(u,v)=1\)，那么 \(a^sb^t=e\) 当且仅当 \(a^s=e,b^t=e\)。
- 若 \(a,b\in G\)，\(a,b\) 的阶分别为 \(u,v\) ，那么定存在元素 \(c\) 使得 \(c\) 的阶 \(w\) 满足 \(w=\operatorname{lcm}(u,v)\)。
置换
置换是有限集合到自己的双射 \(S=\{a_1,\dots,a_n\}\) 表示为：
\[f=\begin{pmatrix}a_1,...,a_n\\ a_{p_1},\dots a_{p_n}\end{pmatrix} \]\(p\) 是一个排列，可以理解为一次映射，不难发现，\(S\) 上的不同置换有 \(n!\) 个。
置换乘法：两个置换的乘法即为两次映射。
不难发现，对于 \(S\) 上的所有置换关于置换乘法满足封闭性、结合律、有单位元（恒等置换，即每个元素映射成它自己）、有逆元（交换置换表示中的上下两行），因此构成一个群。这个群的任意一个 子群 即称为 置换群。
轨道 - 稳定子定理
对于集合 \(S\) 和置换群 \((G,\cdot)\)，以及 \(x\in S\)。
轨道：定义为 \(G(x)=\{g(x)|g\in G\}\)，简单的说就是 \(G\) 中所有元素作用在 \(x\) 上得到的集合。
稳定子：定义为 \(G^x=\{g|g\in G,g(x)=x\}\)， 简单的说就是 \(G\) 中作用在 \(x\) 上使 \(x\) 不变的元素的集合。
轨道 - 稳定子定理：
对于任意 \(x\in S\)，\(|G^x||G(x)|=|G|\)。
证明：
- 引理一：\(G^x\) 为 \(G\) 的子群。
- 封闭性：对于 \(f,g\in G\)，\(f(x)=g(x)=x\)，所以 \((f\cdot g)(x)=x\)，根据 \(G^x\) 定义可知，有封闭性。
- 结合律：\(G\) 满足，所以 \(G^x\) 更满足。
- 存在单位元：有恒等置换做单位元，且满足 \(e(x)=x\)。
- 存在逆元：设 \(g\in G^x\)，\((g\cdot g^{-1})(x)=e(x)=x\) ，根据置换，不难发现 \(g^{-1}(x)=x\)。
- 引理二：\([G:G^x]=|G(x)|\)。
- 考虑 \(g(x)\) 与 \(gG^x\) 一一对应。
- 若 \(f(x)=g(x)\)，则有 \(f\cdot g^{-1}=x=e(x)\in G^x\)，根据陪集性质 \(fG^x=gG^x\)。
- 所以我们证明了：当 \(g(x)\) 相同时 \(gG^x\) 相同。
根据拉格朗日定理：\(|G^x|[G:G^x]=|G|\)。
得到 \(|G^x||G(x)|=|G|\)。
Burnside 定理
若 \((G,\cdot )\) 为置换群，\(X\) 为一个集合，若存在 \(f(x)=y(f\in G,x,y\in X)\)，则定义 \(x,y\) 属于一个等价类。
若 \(X/G\) 表示 \(G\) 作用下 \(X\) 的所有等价类集合，\(X^g\) 表示 \(g\) 作用下不变的 \(X\) 中元素的集合（类似于轨道 - 稳定子定理）。
\(|X/G|=\dfrac{1}{|G|}\sum\limits_{g\in G}|X^g|\)
证明：
\( \begin{aligned} \sum\limits_{g\in G}|X^g|&=\sum\limits_{x\in X}|G^x|\text{（转换枚举贡献的方式）}\\&=\sum\limits_{x\in X}\dfrac{|G|}{|G(x)|}\text{（轨道 - 稳定子定理）}\\&=|G|\sum\limits_{x\in X}\dfrac{1}{|G(x)|}\\&=|G|\sum\limits_{Y\in(X/G)}\sum\limits_{x\in Y}\dfrac{1}{|G(x)|}\text{（先枚举每个等价类，再依次枚举等价类中的元素）}\\&=|G|\sum\limits_{Y\in(X/G)}\sum\limits_{x\in Y}\dfrac{1}{|Y|}\text{（每个等价类中元素的轨道均相同，为等价类集合大小）}\\&=|G||X/G|\end{aligned} \)
Pólya 定理
用 \(m\) 中颜色给 \(n\) 个对象染色在 \(n\) 阶置换群 \(G\) 意义下的方案数为 \(\dfrac{1}{|G|}\sum\limits_{g\in G}m^{c(g)}\)，\(c(g)\) 表示置换 \(g\) 的置换环个数。
证明：考虑每个置换环都只能用同一种颜色。
例题
-
题面：
给定一个 \(n\) 个点，\(n\) 条边的环，有 \(n\) 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 \(10^9+7\) 取模。本质不同定义为：不能通过旋转与别的染色方案相同。
\(n\le10^9,T\le10^3\)。
-
解法：
考虑本题中置换一共 \(n\) 个： \(\{i,\dots,n,1,\dots,i-1\}(1\le i\le n)\) 。
每个置换的置换环个数为 \(\gcd(n,i)\)。
所以：
\[\begin{aligned}ans&=\dfrac{1}{n}\sum\limits_{i=1}^nn^{\gcd(n,i)}\\&=\dfrac{1}{n}\sum\limits_{d|n}n^d\sum\limits_{i=1}^n{[\gcd(n,i)=1]}\\&=\dfrac{1}{n}\sum\limits_{d|n}n^d\sum\limits_{i=1}^{\frac{n}{d}}{[\gcd(\frac{n}{d},i)=1]}\\&=\dfrac{1}{n}\sum\limits_{d|n}n^d\varphi(\frac{n}{d})\end{aligned} \]复杂度 \(O(T\sum\limits_{d|n}\sqrt{d})=O(Tn^{0.75})\)。
感觉有点悬考虑一开始的时候直接对 \(n\) 分解质因数，然后通过 dfs 边枚举因数的同时可以求 \(\varphi\)。
复杂度 \(O(T(\sqrt{n}+\omega(n)\log(n)))\)，可过。
不过题解区很多好像都是上面暴力过的。
-
题面：
给定 \(12\) 根等长，着色的木棒。问能构成的本质不同的正方体数量。颜色最多有 \(6\) 种。
正方体 \(A\) 和 \(B\) 本质不同，当 \(A\) 不能通过旋转得到 \(B\) 。
-
解法：
颜色数量有限制，考虑使用 Burnside。
转正方形，考虑先手玩把所有置换给玩出来。
然后就可以 \(6\) 维 dp，不过上天了。
然后就是感觉比较牛的东西：这些置换中的一部分是同构的。
准确的说：\(6\) 面，每面 \(4\) 种共 \(24\) 种置换可以分成 \(1\) 个 \((1)^{12}\)，\(3\) 个 \((2)^6\)，\(8\) 个 \((3)^4\)，\(6\) 个 \((4)^3\) ，以及 \(6\) 个 \((1)^2(5)^2\)。
前面四种都可以组合数搞，最后一种枚举 \(2\) 个 \(1\) 也可以组合数。
-
题面：
有色图是一张每条边都被染成了一种颜色的无向完全图。不同定义为不能经过某种顶点编号的重排，使得两张图对应边的颜色相同。
求所有顶点数为 \(n\)，颜色种类不超过 \(m\) 的不同有色图的方案数，模 \(p\)。
\(1\leq n\leq 53\)，\(1\leq m\leq 1000\)，\(n<p\leq 10^9\)。
-
解法：
给每条边染色，但是同构的定义是点的重排，所以考虑对于共 \(n!\) 个排列，计算贡献。
对于其中一个排列把它拆成若干个置换环，设环长依次为 \(a_1,a_2,\dots,a_k\)，边等价类有以下两种：
- 一个置换环内：同样距离的两对点所对应的边，属于同一个等价类（考虑在环上依次为 \(1,2,3,4\)，那么边 \((1,3)\) 在环上转一次变成 \((2,4)\)，属于一个等价类），若环长为奇数不同长度有 \(\frac {n-1}2\) 种，偶数不同长度有 \(\frac n 2\) 种。
- 不在一个置换环内：这两点出现的周期为 \(\operatorname{lcm}(a_i,a_j)\)，所以不同等价类个数为 \(\frac{a_i a_j}{\operatorname{lcm}(a_i a_j)}\)。
所以一个排列的等价类个数为 \(\sum\limits_{i=1}^n \lfloor \frac a 2 \rfloor+\sum\limits_{i=2}^n\sum\limits_{j=1}^{i-1}\gcd(a_i,a_j)\)
然后就得到一个 \(O(n!n^2\log n)\) 的优秀做法。。。。。。
考虑这个 \(53\) 是什么：整数分拆。
考虑枚举 \(a_1\le a_2 \le \dots\le a_k,\sum_{i=1}^k a_i =n\) ，然后计算有多少个排列是这样的。
\(1\dots n\) 每个点分在每个循环中的方案数是 \(\dfrac{n!}{\prod a_i!}\) ，一个环上的方案数是一个圆排列，即 \(\prod (a_i-1)!\)。
然后相同大小的环会导致算重，设大小为 \(l\) 的环有 \(s_l\) 个，除以 \(s_l!\) 即可。
\[\begin{aligned}ans&=\dfrac 1{n!}\sum\limits_a \dfrac{n!}{\prod a_i!}\prod (a_i-1)!\prod\limits_l\dfrac{1}{s_l!}m^{c}(c=\sum\limits_{i=1}^n \lfloor \frac a 2 \rfloor+\sum\limits_{i=2}^n\sum\limits_{j=1}^{i-1}\gcd(a_i,a_j))\\&=\sum\limits_a \dfrac{1}{\prod a_i \prod s_l!}m^c\end{aligned} \]复杂度：\(O(\)能过\()\)。