简介
burnside引理
置换
有限集合到自身的双射成为置换，集合 $S=\lbrace a_1,a_2,\cdots,a_n\rbrace$ 上的置换可以表示为 $f=\dbinom {a_1~a_2~…~a_n} {a_{p_1}~a_{p_2}~…a_{p_n}} $，$f(a_k)=a_{p_k}$
两个置换的合成 $(g\circ f)(k)=g(f(k))$
简单来说，置换群就是群中的所有元素都是置换的群
着色
设 $c$ 为 $S$ 的一种着色，$a_1,a_2,\cdots,a_n$ 的着色分别为 $c(a_1),c(a_2),\cdots,c(a_n)$
着色与置换的合成 $(f\times c)(a_{p_k})=c(a_k)$，$(f\times c)(a_k)=c(f^{-1}(a_k))$，容易得到 $(g\circ f)\times c=g\times (f\times c)$
置换与着色的关系
如果存在 $f\in G$，$f\times c_1=c_2$ 则称 $c_1$ 与 $c_2$ 等价
等价关系的性质：
- 自反性：$\forall c\in C,c\sim c$
- 对称性：$\forall c_1,c_2\in C$，如果 $c_1\sim c_2$，则 $c_2\sim c_1$
- 传递性：$\forall c_1,c_2,c_3\in C$，如果 $c_1\sim c_2$，$c_2\sim c_3$，则 $c_1 \sim c_3$
定义：$G(c)=\lbrace f|f\in G,f\times c=c\rbrace$ 为使着色 $c$ 保持不变的 $G$ 中所有置换的集合
定义：$C(f)=\lbrace c|c\in C,f\times c=c\rbrace$ 为在 $f$ 的作用下，保持不变的 $C$ 中所有着色的集合
定理：对于每一种着色 $c$，$G(c)$ 是置换群，对于 $G$ 中的置换 $g$ 和 $f$，$g\times c=f\times c$ 当且仅当 $f^{-1}\circ g\in G(c)$
推论：设 $c$ 为 $C$ 中的一种着色，则与 $c$ 等价的着色数为 $\frac{|G|}{|G(c)|}$
证明：
设 $f$ 是 $G$ 中的置换，则满足 $g\times c=f\times c$ 的 $g$ 实际上是 $\{f\circ h|h\in G(c)\}$ 中元素，根据消去率，$f\circ h$ 两两不相同，所以 $g$ 的个数为 $|G(c)|$。也就是说，对于每个置换 $f$，恰有 $|G(c)|$ 的置换作用在 $c$ 上和 $f$ 的效果相同，所以与 $c$ 的等价的着色的个数为 $\frac{|G|}{|G(c)|}$
我们按照 $c$ 的等价关系可以将 $c$ 划分成若干个等价类
所以我们定义 $A(c)$ 表示 $c$ 所在的等价类
burnside引理
令 $L$ 为等价类的个数，则 $L=\frac{1}{|G|}\sum_{f\in G}C(f)$
polya定理
当颜色数为 $m$ 时，即每个对象可以染 $m$ 种颜色中的任意一种，$C(f)=m^{d(f)}$，其中 $d(f)$ 为 $f$ 的循环个数
几种特殊置换的循环个数
- $p_i=i+k$，循环个数为 $(n,k)$
例题
简要题意：给定 $n$ 和 $m$，求有多少本质不同的序列 $a_i$，满足 $0\le a_i<m$，且 $a_i$ 可以重复循环左移任意次以及整体重复加任意次，对于 $k\in[1,n]$ 计算答案
$n,m\le 10^5$
简要题解：注意到本质不同等价于求有多少长度为 $n$，每一位的大小为 $[0,m-1]$ 且和模 $m$ 为 $0$ 的圆环，我们首先不考虑最后一个条件，那么这显然是一个 $burnside$ 定理的题目，我们有 $n$ 个置换 $f$，第 $k$ 个置换满足 $p_i=i+k$，且第 $k$ 个置换有 $(n,k)$ 个循环，每个循环的大小都是 $\frac{n}{(n,k)}$，同时数字大小为 $[0,m-1]$ 相当于有 $m$ 种颜色，那么我们可以得到对于长度为 $n$ 的环，答案为 $\sum_{i=1}^n m^{(n,i)}$
我们现在考虑和模 $m$ 为 $0$ 这个条件，我们不妨设环大小为 $d$，环个数为 $\frac{n}{d}$，第 $i$ 个环的颜色为 $a_i$，那么我们必须有 $d\sum_{i=1}^{\frac{n}{d}}a_i\equiv 0(\bmod m)$，这个东西等价于 $\sum_{i=1}^{\frac{n}{d}}a_i\equiv 0(\bmod \frac{m}{(m,d)})$，我们知道 $a_i$ 在 $[0,m-1]$ 内均匀取值，那么 $\sum a_i\equiv k(\bmod m)$，其中 $k\in[0,m-1]$，的方案数是相同的，所以这个东西占总数的比列就是 $\frac{(m,d)}{m}$，那么原式就是 $\sum_{i=1}^nm^{(n,i)}\frac{(m,\frac{n}{(n,i)})}{m}$，这个东西我们化简一下可以得到 $\frac{1}{nm}\sum_{d|n}m^{d}\varphi(\frac{n}{d})(m,\frac{n}{d})$
时间复杂度 $O(n\log n)$
简要题意：给定 $n,m$，求有多少本质不同的序列 $a_i$，每个位置可以填 $[1,m]$，现在还有 $k$ 个序列变换的方法，第 $i$ 个方法给定一个 $b_i$，保证所有 $b_i$ 互不相同且 $b_i\le \lfloor\frac{n}{2}\rfloor$，第 $i$ 种方法表示交换 $[1,b_i]$ 和 $[n-b_i+1,n]$ 的元素，交换顺序为 $i$ 和 $n-i+1$ 交换，两个序列本质不同定义为不能通过使用若干次变换方法变得相同
$n,m\le 10^9,k\le 10^5$
简要题意：考虑 $burnside$，注意到有 $2^k$ 个置换，另外我们注意到将 $b_i$ 差分后不影响置换的个数，差分后我们发现不同的交换方法叠加到一起不会相互影响，那么我们直接维护 $m^{n-\sum t_i},t_i$ 表示选择的 $b_i$
简要题意：求有多少个长度为 $n$ 的循环同构的序列，每个位置最多只有三种颜色，红绿蓝，要求绿色不能出现超过 $k$ 次，且相邻的位置颜色不能相同
$n,k\le 10^6$
简要题解：首先我们知道答案就是这个式子 $\frac 1 n \sum_{i=1}^n\sum_{j=0}^{\lfloor \frac{m(i,n)}{n}\rfloor}f((i,n),j)$ 其中 $f(n,m)$ 表示大小为 $n$ 的环染色，其中绿色的个数为 $m$
首先我们考虑如何计算 $f(n,m)$
首先我们考虑绿色不放在 $1$ 或 $n$ 的位置，那么两个绿色之间有且仅有两种填法，那么答案就是 $2^m\binom{n-m}{m}$
然后我们考虑将绿色放在 $1$ 或 $n$ 的位置，容易知道这两种情况的方案数相同，下面仅考虑放在 $1$ 的情况，容易得到答案是 $2^{m-1}\binom{n-m-1}{m-1}$，注意这个东西还要乘个 $2$
那么 $f(n,m)=2^m(\binom{n-m}{m}+\binom{n-m-1}{m-1})$
我们考虑化简总的答案，容易得到 $\frac 1 n \sum_{d|n} \varphi(\frac n d)\sum_{i=0}^{\lfloor \frac{m(i,n)}{n}\rfloor}f(d, i)$
我们直接枚举约数然后 $O(n)$ 计算即可