前言
做多项式题就像嗑药，出多项式题就像贩毒。—— 某 FJ 知名 OI 选手
多项式对 OI 是非常重要的，一些经典的运用比如线段树维护幺半群，或者是 Polya 定理，数论的一些特例结论，本文希望总结一些多项式教学的相关内容。
我们认为你在阅读本文前拥有高中数学水平。
抽象代数速成
基本知识
集合 \(A,B\) 的笛卡尔积为 \(A \times B={(a,b)|a \in A,b \in B}\)。
集合 \(A\) 上的一个二元映射是 \(A \times A \rightarrow A\)，一个二元关系是 \(A \times A\) 的子集（不需要映射到 \(A\)）
群论
群的概念
定义：非空集合 \(G\) 上定义了一个二元关系 \(\cdot\)，满足：
- 结合律，即 \((a \cdot b) \cdot c=a \cdot (b \cdot c)\)。
- 幺元存在，即存在 \(e \in G\) 使得 \(e \cdot a=a \cdot e=a\)
- 逆元存在，对于所有 \(a \in G\)，都存在 \(b \in G\) 使得 \(a \cdot b= b \cdot a=e\)
则称 \(G\) 关于运算 \(\cdot\) 构成一个群，记为 \((G,\cdot )\)，群的幺元唯一，逆元唯一，且满足消去率。
常见的群
- \((\Z,+),(R/\{0\},\times)\)
- 对称群：集合 \(M\) 上的所有置换，即自 \(M\) 到 \(M\) 的双射，构成群 \(S_M\)
- 交错群：\(S_n\)中所有偶置换（对换分解中对换个数为偶数的置换）构成\(S_n\)的子群，称为\(n\)级交错群，记为\(A_n\)。
需要注意的是，正整数关于加法并不是一个群，因为逆元不存在。
弱化的群
- 半群是只满足结合律的群
- 存在幺元的半群是幺半群
Abel 群
我们将 \(a \cdot b=b \cdot a\) 的群称为 Abel 群：
- 整数加法是 Abel 群。
- \(n \ge 3\) 时，对称群 \(S_n\) 并非 Abel 群。
子群的定义与等价命题
设\(G\)为群，\(H\)为\(G\)的非空子集。若\(H\)在\(G\)的运算下自身构成群，则称\(H\)为\(G\)的子群，记为\(H \leq G\)。
子群的等价判别条件（只需满足其一）：
- 封闭性与逆元存在：对任意\(a,b \in H\)，有\(a \cdot b \in H\)且\(a^{-1} \in H\)；
- 逆乘积封闭：对任意\(a,b \in H\)，有\(a \cdot b^{-1} \in H\)（或写作\(H^{-1}H \subseteq H\)，其中\(H^{-1} = \{h^{-1} \mid h \in H\}\)）。
注意：证明\(H\)为子群时，必须先验证\(H\)非空（通常取单位元\(e \in H\)，或存在某个元素\(a \in H\)）。
由子集生成的子群
对于群 \(G\) 和它的非空子集 \(S \subseteq G\)，如果 \(H\) 是包含 \(S\) 的 \(G\) 的子群中（包含关系）最小的，则子群 \(H\) 称为由子集 \(S\) 生成的子群，并记作 \(\langle S \rangle\)。特别地，如果 \(S = \{x\}\) 是单元素集合，则 \(\langle S \rangle\) 也记作 \(\langle x \rangle\)，称为由元素 \(x\) 生成的子群，一个元素生成的群被称为循环群。
如果群 \((G,\cdot)\) 的子集 \(S \subseteq G\) 满足 \(\langle S \rangle = G\)，则称 \(S\) 是 \(G\) 的生成子集。生成子集 \(S\) 中的元素称为生成元。
阶
阶是群所含元素的个数，记为 \(|G|\)。\(|G|\) 有限称为有限群，否则称为无限群。
元素 \(x\) 的阶是最小的 \(n\) 使得 \(x^n=e\)，如果没有这样的阶，\(|x|=\infin\)
陪集，Lagrange 定理和其他
设 \(G\) 是群，\(H \leq G\) 是它的子群，则子群 \(H\) 的包含 \(g\) 的左陪集和右陪集分别定义为集合：
\(gH = \{gh = h \in H\}\)
\(Hg = \{hg = h \in H\}\)
陪集中的元素称为陪集的代表元。
子群本身也是其陪集。给定子群，全体陪集构成群的一个分划，即群是全体陪集的不交并。分划总可以看作某个等价关系的等价类。
同一子群的不同陪集大小都相同，都等于对应子群的大小。由于给定子群的全体陪集构成群的一个分划，有限群的阶必然是子群的阶的整数倍。这叫做 Lagrange 定理。
经典应用：模 \(n\) 整数乘法群的阶为 \(\varphi(n)\)，所以 \(x \in (\Z/n\Z,\times),x^{\varphi(n)}=1\)，这就是欧拉定理。
正规子群是左右陪集相同的子群，如果 \(H\) 是 \(G\) 的一个正规子群，\(h \in H,g \in G,ghg^{-1} \in H\)，记作 \(H \unlhd G\)。
考虑陪集的集合和运算 \(G/N=\{gN|g \in G\},g_1N \circ g_2N=(g_1g_2)N\)，\((G/N,\circ)\) 就是 \(G\) 模 \(n\) 的商群，简单来说，就是为群去除了一些特征。
群同态
同态与同构的概念
设 \(\varphi:(G,\cdot) \rightarrow (H,\circ)\) 是一个映射，如果 \(\varphi(g_1 \cdot g_2) = \varphi(g_1) \circ \varphi(g_2)\)，\(\varphi\) 是群 \(G\) 到群 \(H\) 的同态，特别的，如果 \(\varphi\) 是双射，则称 \(G\) 和 \(H\) 同构，记作 \(G \cong H\)。
同态可能对群的性质造成损失，我们称 \(\ker\varphi =\{g \in G:\varphi(G)=e\}\) 为同态的核。
同态基本定理
设 \(\varphi: G \to H\) 是自群 \(G\) 到群 \(H\) 的同态，则 \(\ker \varphi \unlhd G\)，且 \(G/\ker \varphi \cong \varphi(G) \leq H\)。
首先令 \(S = \ker \varphi\)，根据定义 \(s \in S,\varphi(gsg^{-1})=\varphi(g)\varphi(g^{-1})=e\)，所以 \(\ker \varphi \unlhd G\)，考虑映射 \(\phi:G/N \to \varphi(G)\)，易知这是满射，发现它也是单射，所以 \(\phi\) 是群同构。
为了深刻理解同态基本定理的本质，对于 \(N \unlhd G\) 引入 \(\pi(g)=gN\)，满足 \(\pi:G \to G/N\)，这个映射就是自然映射。
群的同构定理
第二同构定理：设群 \(G\) 和子群 \(A,B \leq G\) 满足 \(A \leq N_G(B)\)，那么 \(AB \leq G\)，且 \(B \unlhd AB\)，\(A \cap B \unlhd A\)，\(AB/B \cong A/(A \cap B)\)。
注：对于群 \(G\) 和它的子集 \(S \subseteq G\)，子集 \(S\) 在群 \(G\) 中的正规化子是 \(N_G(S) = \{ g \in G : gSg^{-1} = S \}\)，\(A \leq N_G(B)\) 的一个充分条件是 \(B \unlhd G\)。
证明：\(A \leq N_G(B) \Rightarrow aBa^{-1}=B \Rightarrow aB=Ba \Rightarrow AB=BA \Rightarrow B \unlhd AB\)，剩下两个易得。
第三同构定理：设群 \(G\) 有正规子群 \(H,K \unlhd G\)，且 \(H \leq K\)，则 \(K/H \unlhd G/H\)，且 \((G/H)/(K/H) \cong G/K\)。
第四同构定理：设群 \(G\) 有正规子群 \(N \unlhd G\)，则全体包含 \(N\) 的群 \(G\) 的子群 \(\mathcal{H} = \{ H : N \subseteq H \subseteq G \}\) 和商群 \(G/N\) 的全体子群 \(\mathcal{S} = \{ S : S \leq G/N \}\) 之间存在双射 \(\varphi: \mathcal{H} \to \mathcal{S}\)，它将 \(H \in \mathcal{H}\) 映射至 \(H/N \in \mathcal{S}\)。这个双射保持子群的包含关系，且 \(G\) 的正规子群总是映射到 \(G/N\) 的正规子群。
循环群性质 1
循环群的结构由其大小唯一确定。如果大小无限，其与整数的加法群 \((Z,+)\) 同构，如果大小有限，它与整数模 \(n\) 的同余类的加法群 \(\Z/n\Z\) 同构，分别记作 \(C_n,\Z_n\)，这个证明留作习题。
群作用
群作用的概念
对于群 \(G\) 和集合 \(X\) 以及映射 \(G \times X \to X\)，记 \((g,x)\) 在该映射下的像为 \(g \cdot x\)，如果该映射对所有 \(g_1,g_2 \in G\) 和 \(x \in X\) 都满足条件 \(g_1 \cdot (g_2 \cdot x) = (g_1g_2) \cdot x\) 和 \(e \cdot x = x\)，那么就称该映射为群 \(G\) 在集合 \(X\) 上的群作用。
轨道和稳定化子
对于群 \(G\) 在集合 \(X\) 上的作用和 \(x \in X\)，称 \(x\) 在群 \(G\) 作用下的轨道是子集 \(Gx = \{ g \cdot x : g \in G \}\)，称群 \(G\) 中 \(x\) 的稳定化子是子群 \(G_x = \{ g \in G : gx = x \}\)，群作用的核就是集合中所有元素的稳定化子的交。
轨道稳定子定理：对于有限群 \(G\) 在集合 \(X\) 上的作用和 \(x \in X\)，有 \(|Gx| = [G : G_x] = |G|/|G_x|\)。
burnside 引理
对于群 \(G\) 在集合 \(X\) 上的作用，轨道的个数等于群中每个元素对应置换的不动点的平均个数，即
\(|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|\).
这里，\(X^g = \{ x \in X : gx = x \}\) 是元素 \(g \in G\) 对应置换的不动点集合。
Cayley 定理
群 \(G\) 同构于对称群 \(S_G\) 的子群，如下：
\(\begin{aligned}
\varphi:G\rightarrow S_G&\\
g\mapsto \varphi_g&: G\rightarrow G\\
&\quad x\mapsto gx
\end{aligned}\)
共轭作用
\(\begin{aligned}
\varphi:G\rightarrow S_G&\\
g\mapsto \varphi_g&: G\rightarrow G\\
&\quad x\mapsto gxg^{-1}
\end{aligned}\)
贺一段共轭相关的概念：
- 对于群 \(G\) 和 \(g \in G\)，元素 \(g\) 在群 \(G\) 中的共轭类是共轭作用下 \(g\) 的轨道。如果元素 \(g\) 和 \(h\) 处在同一共轭类中，则称 \(g\) 和 \(h\) 共轭。
- 对于群 \(G\) 和 \(a \in G\)，元素 \(a\) 在群 \(G\) 中的中心化子是 \(C_G(a) = \{ g \in G : ga = ag \}\)。
- 对于群 \(G\)，群 \(G\) 的中心为 \(Z(G) = \cap_{a \in G} C_G(a) = \{ g \in G : \forall a \in G \ (ga = ag) \}\)。
- 对于群 \(G\)，设 \(\{X_i\}_{i=1}^r\) 为全体长度大于一的共轭类，且 \(g_i\) 是 \(X_i\) 的代表元，成立 \(|G| = |Z(G)| + \sum_{i=1}^r [G : C_G(g_i)]\)。
Sylow 定理
哎呀我不会，长大后再学习。
环论
对于非空集合 \(R\) 和其上的两个二元运算 \(+ : R \times R \to R\) 和 \(\cdot : R \times R \to R\)，如果它们满足以下性质，则称 \((R, +, \cdot)\) 是一个环：
- \((R, +)\) 构成 Abel 群，其单位元记作 \(0\)，元素 \(a \in R\) 在 \(+\) 下的逆元记作 \(-a\)。
- \((R, \cdot)\) 构成半群，即 \(\cdot\) 满足结合律。
- 分配律：对于所有 \(a,b,c \in R\)，成立 \(a \cdot (b + c) = a \cdot b + a \cdot c\) 和 \((a + b) \cdot c = a \cdot c + b \cdot c\)。
加法单位元