群论
//听说noip不考群论 那先不学了
群
群：给集合 \(G\not= \varnothing\) 的元素定义一个二元运算 \(\cdot\)，记作群 \((G,\cdot)\)，其应满足如下性质
-
封闭性：对于所有 \(G\) 中 \(a,b\) ，运算 \(a\cdot b\) 的结果也在 \(G\) 中。
-
结合律：对于 \(G\) 中所有 \(a,b,c\) ，等式 \((a\cdot b)\cdot c=a\cdot (b\cdot c)\) 成立。
-
标识元： \(G\) 中存在一个元素 \(e\)，使得对于 \(G\) 中的每一个元素 \(a\) ，都有一个 \(e\cdot a=a\cdot e=a\) 成立。这样的元素具有独一性，被称作群的标识元素。
-
逆元：对于每个 \(G\) 中的 \(a\) ，总存在 \(G\)中的一个元素 \(b\) 使 \(a\cdot b=b\cdot a=e\) ，称 \(b\) 为 \(a\) 的逆元，记为 \(a^{-1}\)。
环：涉及两个二元运算， \((G,\cdot)\)和\((G,+)\) ，其中前者是个可交换群，即满足交换律，后者是个半群，即仅满足封闭性和结合律而忽略标识元和逆元的群。
群同态：群论中两个群保持乘法关系的一种映射，可用于关联两个群。从群 \((G,\cdot)\)到群 \((H,+)\) 的同态是一个函数 \(\varphi:G \to H\) 使得对于 \(G\) 中所有的元素 \(a\) 和 \(b\) 有 \(\varphi(a\cdot b)=\varphi(a)+\varphi(b)\) 。
子群：若 \((G,\cdot)\)和 \((H,\cdot)\) 都是群，且 \(H\) 是 \(G\) 的非空真子集，则称 \((H,\cdot)\) 是 \((G,\cdot)\) 的子群，且 \(G\) 的单位元素必包含在 \(H\) 中。
子群检验法：对于所有元素 \(g,h\in H\) ，只需检查 \(g^{-1}\cdot h \in H\)。
陪集：陪集是一个群的子集，是将群的一个固定元素乘以给定子集的每个元素在左边或右边所得到的所有乘积的集合，即：
\(gH=\{g\cdot h \mid h\in H\}\).
\(Hg=\{h\cdot g \mid h\in H\}\).
商群： \(G/N=\{gN \mid g\in G\}\).
共轭：如果群中有一个元素 \(g\) 使得 \(b=g^{-1}ag\) ，群的两个元素 \(a\) 和 \(b\) 是共轭的。这是一个等价关系，其等价类称为共轭类。
阶：
群 \(G\) 中元素 \(x\) 的阶，是指存在一个最小正整数 \(d\) ，使得 \(x^d=e\)。 对于有限群，元素 \(x\) 的阶一定存在。
群 \(G\) 的阶就是群 \(G\) 元素的个数。对于无限群 \(G\) ，阶规定为 \(0\) 。
定理1：群中任意一个元素的阶，一定整除群的阶。
定理2：若群中存在两个元素 \(a\) 、 \(b\) 的阶 \(m\) 、 \(n\) 互素，那么当且仅当 \(a^s=e\) 且 \(b^t=e\) 时 \(a^sb^t=e\)。
定理3：若群 \(G\) 中存在两个元素 \(x_1\) 、 \(x_2\) 的阶是 \(d_1\) 、 \(d_2\) ，那么 \(G\) 中一定存在元素 \(x\) ，阶为 \(d=lcm(d_1,d_2)\)。
循环节：群 \(G\) 中的每个元素 \(a\) 都可以表示为 \(a=g^k\) ，其中 \(k\) 为整数，称 \(g\) 为群 \(G\) 的生成元，且生成元 \(g\) 的阶就是循环群 \(G\) 的阶。
置换群
置换：有限集合到自身的双射（一一对应）称为置换。集合 \(S=\{a_1,a_2,\dots,a_n\}\) 上的置换可以表示为
\[f=\begin{pmatrix} a_1,a_2,\cdots ,a_n\\ a_{p_1},a_{p_2},\cdots,a_{p_n}\\ \end{pmatrix} \]指将 \(a_i\) 映射为 \(a_{p_i}\) ，其中 \(p_1,p_2,\cdots,p_n\) 是 \(1,2,\cdots,n\)的一个排列。显然 \(S\) 是所有置换的数量为 \(n!\)。
置换的乘法：
对于两个置换 \(f=\begin{pmatrix}a_1,a_2,\cdots,a_n\\a_{p_1},a_{p_2},\cdots,a_{p_n} \end{pmatrix}\) 和 \(g=\begin{pmatrix}a_{p_1},a_{p_2},\cdots,a_{p_n} \\a_{q_1},a_{q_2},\cdots,a_{q_n} \end{pmatrix}\) ， \(f\times g=\begin{pmatrix}a_1,a_2,\cdots,a_n\\a_{q_1},a_{q_2},\cdots,a_{q_n} \end{pmatrix}\) ，可看作先经过 \(f\) 的映射，再经过 \(g\) 的映射。
置换群：集合 \(S\) 上所有置换都可以看作一个群，该群任意一个子群即称为置换群。
循环置换：