群论小记
模拟赛的时候一看 T4，哦旋转，哦本质不同，哦群论啊，我不会啊，然后就被区分了，于是痛定思痛来学习一下尝试入门很多次但是失败了的群论。
这篇文章以我的方式理清楚了 Burnside 引理的证明过程，有些认为不重要的就跳了，有些重要的也跳了。
群
群的定义
我们称一个集合 \(G\) 和二元运算 \(\times\) 的满足以下性质的二元组 \((\times,G)\) 为群：
- 封闭性：若 \(a\in G,b\in G\)，则 \(a\times b\in G\)。
- 单位元：存在 \(e\in G\)，满足 \(a\times e=e\times a\in G\)。
- 结合律：\((a\times b)\times c=a\times (b\times c)\)。
- 逆元：对于每个 \(a\in G\)，有 \(b\in G\) 满足 \(a\times b=e\in G\)。
子群
若对于群 \(G\)，有 \(H\subset G\)，且 \((\times ,H)\) 是一个群，那么我们称 \(H\) 是 \(G\) 的一个子群。
我们定义一个类似于运算的东西：对于某个 \(g\in G\) 记 \(gH\) 表示所有 \(g\times h,h\in H\) 组成的的集合。称 \(gH\) 为 \(H\) 在 \(G\) 内关于 \(g\) 的陪集。
陪集主要有一个最重要的性质：\(aH \cap bH\not=\empty\to aH=bH\)。
证明：设 \(c\in aH\)，且 \(c\in bH\)，则存在 \(h_1,h_2\in H,a\times h1=b\times h2=c\)。移项得到 \(a\times b^{-1}=h2\times h1^{-1}\in H\)，则 \(a\times b^{-1}H=H\)，那么 \(aH=bH\)。
拉格朗日定理
若 \(H\) 是 \(G\) 的子群， 记 \(G/H\) 表示 \(G\) 中所有 \(H\) 的陪集，\([G:H]\) 表示 \(G\) 中 \(H\) 本质不同的陪集数量。
拉格朗日定理说的是 \([G:H]\times |H|=|G|\)。这条定理可以通过上面陪集的性质得到。
置换
详见 OIwiki，排列组合基础？
置换群
我们观察置换和置换的合成这样的二元组，可以发现这是一个群。
群作用
通俗地来讲，就是一个群中的元素对于一个集合元素满足结合律的某种变换。
形式化的，设有函数 \(\varphi(x,y)\)，其中 \(x\) 是群 \(G\) 的元素，\(y\) 为集合 \(M\) 的元素，满足：
- \(\varphi(e,y)=y\)
- \(\varphi(b,\varphi(a,y))=\varphi(a\times b,y)\)
那么称 \(G\) 作用于 \(M\)。
轨道-稳定子定理
轨道是指集合 \(M\) 中某个元素 \(x\) 经过群 \(G\) 中的元素能转移到的元素。
稳定子指对于某个元素 \(x\)，\(G\) 中的元素 \(g\) 满足 \(\varphi(g,x)=x\)。
根据拉格朗日定理，你大概可以感觉出来稳定子的个数乘以轨道大小就是群的大小，事实上也是这样但我不会证明。
Burnside 定理
终于到重头戏了。
定义 \(G\) 为一个群，作用于 \(M\)，则 \(x,y\in M\) 相同当且仅当存在 \(g\in G\) 满足 \(\varphi(g,x)=y\)。则其等价类数目为 \(\frac{1}{|G|}\sum\limits_{g\in G}{M^{g}}\)。其中 \(M^g\) 表示 \(g\) 作用下的不动点个数。
我们想要让一个环算一次，那么怎么办？只需要让环上每个点的贡献是环长的倒数即可，也即轨道的大小的倒数。又因为轨道是等于 \(\frac{|G|}{M^g}\) 的，因此可以得到 Burnside 定理
但是这个东西有啥用呢？我们来考虑某道 模板题。
在这道题中群内的元素为旋转 \(\frac{2k\pi}{n}\)，其中 \(0\leq k<n\)，我们想要计算在旋转某个角度下的不动点个数，也就是说有长度为 \(k\) 的循环节。又因为循环节一定整除 \(n\)，所以应该有一个 \(\gcd(n,k)\) 的循环节，也即我们要求 \(\sum\limits_{i=1}^{n}{n^{\gcd(i,n)}}\)。
外层枚举 \(\gcd\) 变成 \(\sum\limits_{i\mid n}{n^i\varphi(\frac{n}{i})}\)，大力枚举计算 \(\varphi\) 即可。
时间复杂度 \(O(Tn^{\frac{3}{4}})\) 但是显然跑不满。