提示: 本文并非严谨的数学分析，有很多地方是自己瞎口胡的，仅供参考。有错误请不吝指出 :p
## 1. 群
### 1.1 群的概念
群 $(S,\circ)$ 是一个元素集合 $S$ 和一种二元运算 $ \circ $ 的合称，其满足以下性质。
##### 封闭性
>对于 $\forall a,b \in S$ ， $\exist c \in S$ 使得 $c = a \circ b$
##### 结合律
>对于 $\forall a,b,c \in S$ ， $a \circ (b \circ c) = (a \circ b) \circ c$
##### 单位元
>$\exist I \in S$ ，使得对于 $\forall a \in S$ ， $a \circ I = I \circ a = a$
根据定义，单位元具有唯一性，即一个群只有一个单位元。
证明：设 $a,b$ 都是 $S$ 的单位元，则 $a = a \circ b = b$ ，两者实质上相同。
##### 逆元
>对于 $\forall a \in S$ ， $\exist a^{-1} \in S$ ，使得 $a \circ a^{-1} = a^{-1} \circ a = I$
根据定义，逆元具有唯一性，即每个元素有且仅有一个逆元。
证明：设 $a$ 有两个逆元 $b,c$ ，则 $b = b \circ I = b \circ (a \circ c) = (b \circ a) \circ c = I \circ c = c$ ，两者实质相同。
这也同时说明了不存在两个元素 $a, b$ 的逆元是同一个元素 $c$，因为 $c$ 只有唯一一个逆元。
即逆元是一一对应的。
### 1.2 更抽象的群
我们更进一步，将 $S$ 中的每一个元素视为一个函数， 默认 $\circ$ 代表函数的复合，即 $(f \circ g) (x) = f(g(x))$。所以现在一个群可以只用一个函数集合 $S$ 来表示。
例如，记 $r_\theta (x)$ 表示将 $x$ 旋转 $\theta$ 度，那么 $S = \{ r_{0^\circ}, r_{90^\circ},r_{180^\circ},r_{270^\circ}\}$ 就是一个群。
证明一下，显然有封闭性和结合律。
单位元是 $r_{0^\circ}$ ，因为 $r_{0^\circ} (r_\theta(x)) = r_{\theta^\circ} (r_0 (x)) = r_\theta(x)$
$S$ 中元素 $r_\theta $ 的逆元便是 $r_{360^\circ - \theta}$ ，因为他们两个卷起来就是 $I = r_{0^{\circ}}$
### 1.3 提示
由于群满足封闭性，所以我们在寻找群的时候一定要“找完”所有可能的状态，例如 $\{ r_{0^\circ}, r_{90^\circ}\}$ 就不是一个群。
## 2. Burnside
首先明确这个定理是用来干什么的——等价类计数。
注：通常我使用 $a,b,c,d \in C$ 表示计数对象， $f,g,h \in G$ 表示变换。
### 2.1 等价
>给定一个作用在计数集合 $C$ 上的变换集合 $G$，若 $C$ 中计数对象 $d$ 可以由计数对象 $c$ 通过 $G$ 中变换得到，即 $\exist f \in G$ 使得 $d = c \circ f$，我们便称 $c$ 与 $d$ 等价，记作 $c \sim d$ 。
$G$ 其实就是个函数集合，其中的函数都接受 $C$ 中元素作为参数，输出也是 $C$ 中元素。
类似的我们记 $f(c)$ 为 $c \circ f$ ，表示对计数对象 $c$ 做变换 $f$ 。
我们同样可以对一个函数做变换，即 $f \circ g$ 是允许的。请参考上文“1.2 更抽象的群”。
在Burnside中，**我们要求 $G$ 是一个群**。这样我们可以导出一些关于等价的性质。
##### 自反性
>$a \sim a$
因为 $G$ 是群，故有单位元 $I \in G$ ， $a \circ I = a$ ，满足等价定义。
##### 对称性
>$a \sim b \iff b \sim a$
设 $a \circ f = b$ ，因为 $G$ 是群，故存在 $f^{-1}$ 使得 $b \circ f^{-1} = a$ ，满足等价定义。同理反向再证一次即可得出充分完全性。
##### 传递性
>$a \sim b , b \sim c \Rightarrow a \sim c$
设 $a \circ f = b, b \circ g = c$，因为 $G$ 是群，所以 $f \circ g \in G$（封闭性），$a \circ (f \circ g) = (a \circ f) \circ g = b \circ g = c$，满足等价定义。
### 2.2 等价类及等价类计数
等价类即所有等价的计数元素的集合。计数集合 $C$ 由许多个等价类构成，好比连通块。 统计 $C$ 中有多少个等价类，就是等价类计数。
如何快速的等价类计数，便是我们接下来所研究的。
### 2.3 弱化版
不妨先来研究一个弱化版本，这可以帮助我们捋清思路。
#### 2.3.1 引理
>若对于 $\forall c \in C,f \in G \quad (f \not= I)$ ， $c \circ f \not= c$ 都成立，那么对于 $\forall c \in C, f \in G,g \in G \quad (f \not= g)$ ，都有 $c \circ f \not= c \circ g$ ，即与 $\forall c$ 等价的元素有且仅有 $|G|$ 个。
利用反证法。若 $\exist c,f,g$ 使得 $c \circ f = c \circ g$ ，那么有 $c \circ f \circ g^{-1} = c$ ，即 $c \circ (f \circ g^{-1}) = c$ 。同时因为 $f \not= g$ ，所以 $f \circ g^{-1} \not= I$ 。于是与假设产生矛盾，故引理成立。
对 $c$ 做变换得到的元素两两不同，共有 $|G|$ 种变换，故有且仅有 $|G|$ 个元素与 $c$ 等价。
#### 2.3.2 弱化版Burnside
>若对于 $\forall c \in C,f \in G \quad (f \not= I)$ ， $c \circ f \not= c$ 都成立，那么
>$$
>等价类计数 = \frac{|C|}{|G|}
>$$
这是肉眼可得的结论。由引理，对于 $\forall c$ ，都有且仅有 $|G|$ 个互不相同的元素与其等价。由于等价的传递性，这 $|G|$ 个元素是封闭的，实质上形成了许多个大小为 $|G|$ 的等价类。那么等价类个数自然就是总计数元素个数 $|C|$ 除以每个等价类的大小 $|G|$ 了。
### 2.4 标准版
弱化版的关键之处在于引理， $c \circ f \not= c$ 让我们知道每个 $c$ 有 $|G|$ 个互不相同的元素与其等价。我们将这个条件和这个引理做一些“推广”。
#### 2.4.1 稳定核 & 不动点
>稳定核 $G(c)$ ：对于计数对象 $c$ ，使得 $c \circ f = c$ 的所有变换 $f$ 的集合，即 $\{ f \in G | c \circ f = c \}$
>
>不动点 $C(f)$ ：对于变换 $f$ ，使得 $c \circ f = c$ 的所有计数对象 $c$ 的集合，即 $\{ c \in C | c \circ f = c \}$
注意单个字母 $G$ 代表整个变换集合；而 $G(c)$ 是根据计数元素 $c$ 生成的一个被 $G$ 包含的变换集合；
注意单个字母 $C$ 代表整个计数集合；而 $C(f)$ 是根据变换 $f$ 生成的一个被 $C$ 包含的计数集合。
#### 2.4.2 引理1
>$$
>\sum_{c \in C} |G(c)| = \sum_{f \in G} |C(f)|
>$$
证明：
$$
\begin{aligned}
\sum_{c \in C} |G(c)| &= \sum_{c \in C} \sum_{f \in G} [c \circ f = c] \\
&= \sum_{f \in G} \sum_{c \in C} [c \circ f = c] \\
&= \sum_{f \in G} |C(f)|
\end{aligned}
$$
其实质是更换枚举方式。
#### 2.4.3 引理2
>对于 $\forall c$ ， $G(c)$ 是个群。
分别证明群的四个性质即可。
##### 封闭性
对于 $\forall f,g \in G(c)$ ， $c \circ (f \circ g) = (c \circ f) \circ g = c \circ g = c$ ，所以 $f \circ g \in G(c)$ 。封闭性得证。
##### 结合律
$G(c) \subseteq G$ ，结合律直接由 $G$ 给出。
##### 单位元
$c \circ I = c$ ，所以 $I \in G(c)$ 。（这里的 $I$ 代指 $G$ 的单位元）
##### 逆元
对于 $\forall f \in G(c)$ ， $ c \circ f^{-1} = (c \circ f) \circ f^{-1} = c \circ (f \circ f^{-1}) = c$ ，所以 $f^{-1} \in G(c)$ 。
#### 2.4.4 引理3
>对于 $\forall c$ ，记 $S(c)$ 为与 $c$ 等价的计数元素的集合，有
>$$
>|S(c)| = \frac{|G|}{|G(c)|}
>$$
这个引理与弱化版引理2.3.1是对应关系。请对比起来理解。
我们的证明思路是：对于某个计数元素 $c$ ，求出 对于某个确定的变换 $f$ ，有多少个变换 $g$ 与其作用效果相同，即 $c \circ f = c \circ g$ 。
$$
c \circ f = c \circ g \iff c \circ f \circ g^{-1} = c \iff (f \circ g^{-1}) \in G(c)
$$
即 $f ,g$ 对 $c$ 的作用效果相同 等价于 $f \circ g^{-1}$ 在 $c$ 的稳定核内。
于是对于一个变换 $h \in G(c)$ ，根据群的基本性质，存在唯一的 $g^{-1} = f^{-1} \circ h$ ，使得 $f \circ g^{-1} = h$ 。变换 $h \in G(c)$ ，所以有 $|G(c)|$ 种取值； $f$ 是确定的，根据逆元唯一性， $f^{-1}$ 也是确定的；故 $g^{-1}$ 有 $|G(c)|$ 种取值。又由于逆元的一一对应性， $g$ 有 $|G(c)|$ 种取值。
即对于 $\forall f$ ，都有且仅有 $|G(c)|$ 个 $g$ 与其作用效果相同。
这说明了什么？“作用效果相同”也是一种类似等价的关系，容易证明其具有传递性，于是他们是封闭的。作用效果相同的变换实质上形成 $\frac{|G|}{|G(c)|}$ 个大小为 $|G(c)|$ 的两两相连的连通块或者说“作用效果相同等价类”，合起来构成了整个 $G$ 。我们便知道了 $c$ 通过变换可以变出 $\frac{|G|}{|G(c)|}$ 个不同的计数元素，即与 $c$ 等价的元素有 $\frac{|G|}{|G(c)|}$ 个，引理3证毕。
#### 2.4.5 Burnside
>$$
>等价类计数 = \frac{1}{|G|}\sum_{f \in G} |C(f)|
>$$
$$
\begin{aligned}
\frac{1}{|G|}\sum_{f \in G} |C(f)| &= \frac{1}{|G|}\sum_{c \in C} |G(c)| \quad &\text{...引理1} \\
&= \frac{1}{|G|}\sum_{c \in C} \frac{|G|}{|S(c)|} \quad &\text{...引理3} \\
&= \sum_{c \in C} \frac{1}{S(c)} \\
&= 等价类计数
\end{aligned}
$$
倒数第二个式子，每个元素贡献 $\frac{1}{S(c)}$ ，合起来便是等价类计数。这便是等价类计数的本质。
### 2.5 Burnside的本质
>直接除以4不行，因为前四种找不到4个等价的情况
>
>所以强行把它们补成4个就行了。。。
>
>Burnside就是“强行补”的过程
>
>——zkx
Burnside的精髓就在于此。
Burnside弱化版，实际上是省掉了强行补的部分，使所有有效部分都在 $C(I)$ 。
>可以发现“群”是Burnside的唯一约束
>
>这个约束几乎就是没有约束。。。
>
>所以Burnside是非常通用的等价类计数法
>
>——zkx
## 3. 置换群
（Burnside的内容已经结束，这里开始是Polya了）
### 3.1 置换
一个置换长这样：
$$
(\begin{aligned}
1&,2,3,...,n \\
a_1&,a_2,a_3,...,a_n
\end{aligned})
$$
其中 $a_1,a_2,a_3,...,a_n$ 是一个 $n$ 排列。置换是一个接受序列，输出序列的函数，它表示对每一个 $i$ ，将原序列第 $i$ 个数放到第 $a_i$ 个位置上。
### 3.2 移位置换
一个普通的移位置换长这样：
$$
\tau_n =
(\begin{aligned}
1,2,3,...,n&-1,n \\
2,3,4,...,&n,1
\end{aligned})
$$
即全员右移1位。很自然的可以拓展到 $k$ 位移位置换：
$$
\tau_n^k =
(\begin{aligned}
1,2,3,...&,n-1,n \\
k,k+1,...,n&,1,...,k-1
\end{aligned})
$$
容易发现 $\tau_n^k$ 是 $k$ 个 $\tau_n$ 的复合，所以我们写成乘方的形式。
### 3.3 移位置换图
移位置换 $\tau_n^k$ 所形成的图：考虑将 $n$ 个点排成一个圆圈， $1$ 连 $k$ ， $2$ 连 $k+1$ ，...，$n$ 连 $k-1$ 。
如图便是 $\tau_6^2$ 形成的移位置换图，共有两个环。
### 3.4 移位置换环个数定理
>$\tau_n^k$ 移位置换图中环的个数为 $\gcd(k,n)$ 。
证明的思路同样是已经使用多次的：求出对于一个数 $a$ ，有多少个数 $b$ 与它在同一个环内。
对于 $\forall a,b$ ， $a,b$ 在同一个环内的条件为
$$
\begin{aligned}
a \equiv b + ik \pmod n &\iff \exist i,j \quad s.t. \quad a = b + ik + jn \\
&\iff \exist i,j \quad s.t. \quad ik + jn = a - b \\
&\iff \gcd(k,n) | (a-b) \quad \text{...裴蜀定理}
\end{aligned}
$$
最后两个式子之间的转化运用了二元整数解不定方程的有解条件，即裴蜀定理。
那么这样一来，对于 $\forall a$ ，显然有且仅有 $\frac{n}{\gcd(k,n)}$ 个数与它在同一环内，故共有 $\gcd(k,n)$ 个环。（“在同一环内”传递性导出的封闭性，这个方法在上文已经多次使用到）
## 4. Polya
### 4.1 概念
Polya是等价类计数的一个特殊版本，它的变换群 $G$ 是一个移位置换群，即
$$
G = \{ \tau_n^k \ | \ k \in [0,n), k \in Z \}
$$
显然移位置换群是一个群 ~~废话~~，证明很简单，同样是证明群的四个性质，这里不再赘述。
用人话来说，Polya求解的一类问题计数基于一个环，而通过旋转环能够变得相同的方案算作一种（等价）。
比如经典的模板题： [洛谷P4980 Polya定理](https://www.luogu.com.cn/problem/P4980)
>给定一个 $n$ 个点， $n$ 条边的环，有 $m$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模。
>
>本质不同定义为：只需要不能通过旋转与别的染色方案相同。
### 4.2 推导
有了前面那么多的铺垫，大名鼎鼎的Polya定理现在已经可以自己动手推出来了！
先写出Burnside引理，并套入移位置换
$$
\begin{aligned}
等价类计数 &= \frac{1}{|G|}\sum_{f \in G} |C(f)| \\
&= \frac{1}{n}\sum_{i=1}^n |C(\tau_n^i)|
\end{aligned}
$$
注： $\tau_n^n = \tau_n^0$ ，上面从 $1$ 到 $n$ 的枚举是对的
$|C(\tau_n^i)|$ 是什么？
$\tau_n^i$ 的不动点的个数，即要求 $\tau_n^i$ 移位置换图里同一环上点颜色相同的方案数。（为了做置换后看上去和原来一样）
根据移位置换环个数定理， $\tau_n^i$ 有 $\gcd(n,i)$ 个环。有 $m$ 种颜色给 $\gcd(n,i)$ 个环去染，显然方案数为 $m^{\gcd(n,i)}$ 。我们不局限于本题推而广之，方案数是一个关于环个数 $\gcd(n,i)$ 的函数 $f(\gcd(n,i))$ 。（也可以是关于环大小 $\frac{n}{\gcd(n,i)}$ 的函数，反正最重要的参数是 $\gcd(n,i)$ ）
带入原式
$$
\frac{1}{n}\sum_{i=1}^n f(\gcd(n,i))
$$
诶！这个式子里面有 $\gcd$ ！
不用抑制住冲动，我们按照常见的莫反题目套路来。
$$
\begin{aligned}
等价类计数 &= \frac{1}{n}\sum_{i=1}^n f(\gcd(n,i)) \\
&= \frac{1}{n} \sum_{d|n} f(d) \sum_{i=1}^n [\gcd(n,i)=d] \quad &\text{...把gcd提出来枚举} \\
&= \frac{1}{n} \sum_{d|n} f(d) \sum_{i=1}^{\frac{n}{d}} [\gcd(\frac{n}{d},i)=1] \\
&= \frac{1}{n} \sum_{d|n} f(d) \varphi(\frac{n}{d}) \quad &\text{...欧拉函数定义}
\end{aligned}
$$
好恭喜你可以在 $O(\sqrt n)$ 的优秀时间复杂度里求得答案了！
### 4.3 实现
提示一下实现上的一些细节。
快速幂作为基本技巧就不提了；
欧拉函数直接质因数分解求即可。这里会遇到一个小问题：外面一层枚举因数，里面一层分解质因数，这不 $O(\sum_{d|n} \sqrt d)$ 了吗？
实际上似乎利用数列的放缩之类的黑科技可以证明一个比 $O(n)$ 更紧的上界是 $O(n^{\frac 3 4})$ ，而且实际上跑起来非常的快。（洛谷 $n=10^9$ ， $10^3$ 组数据可以随便跑过）
```c++
/*
洛谷P4980 Polya定理
sun123zxy
朴素写法
洛谷共2.08s
2019/12/24
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
