笔记 数学 Pólya 计数
$\text{Pólya}$ 计数用来解决一些涉及「本质不同」的计数问题。
置换群
如果 $X$ 是前 $n$ 个正整数组成的集合 $[n]$，那么置换 $f$ 可以看成 $X\to X$ 的函数。其中
\[f(1)=i_1,f(2)=i_2,\cdots,f(n)=i_n\]我们往往使用 $2\times n$ 的阵列来表示置换 $f$
\[f=\begin{pmatrix}1&2&\cdots&n\\i_1&i_2&\cdots&i_n\end{pmatrix}\]显然，当 $X=[n]$ 时，置换 $f$ 最多有 $n!$ 种。我们把这 $n!$ 种置换组成的集合称作 $\mathfrak S_n$（这个符号是德文尖角体 $\text{mathfrak}$ 的 $\text S$）。
由于置换是函数，函数可以复合，所以置换也可以复合。
\[f=\begin{pmatrix}1&2&\cdots&n\\i_1&i_2&\cdots&i_n\end{pmatrix},g=\begin{pmatrix}1&2&\cdots&n\\j_1&j_2&\cdots&j_n\end{pmatrix}\\ (g\circ f)(k)=g(f(k))=j_{i_k}\]如果用图论的观点看，$f$ 就是 $k\to i_k$ 的一条有向边，先走 $f$ 再走 $g$ 就相当于 $k\to i_k\to j_{i_k}$ 的路径。
举个例子
\[f=\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix},g=\begin{pmatrix}1&2&3&4\\2&4&3&1\end{pmatrix}\\ (g\circ f)(1)=3,(g\circ f)(2)=4,(g\circ f)(3)=1,(g\circ f)(4)=2\\ g\circ f=\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}, f\circ g=\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}\]显然置换的复合 $\circ$ 并不满足交换律，也就是说 $f\circ g\ne g\circ h$ 一般情况下成立。
可以证明，置换的复合 $\circ$ 满足结合律，也就是说 $(f\circ g)\circ h=f\circ(g\circ h)$ 恒成立。
我们用幂的符号表示置换 $f$ 与自身的复合
\[f^1=f,f^2=f\circ f,f^3=f\circ f\circ f,\cdots,f^n=f^{n-1}\circ f\]定义：恒等置换 $\iota$ 表示各整数对应到其自身的置换，也就是说 $\iota(i)=i$。
\[\iota=\begin{pmatrix}1&2&\cdots&n\\1&2&\cdots&n\end{pmatrix}\]显然 $\iota\circ f=f\circ\iota=f$。由于 $\mathfrak S_n$ 中的所有函数 $f$ 都是双射函数，必然存在且唯一存在 $f^{-1}\in \mathfrak S_n$ 满足 $f\circ f^{-1}=f^{-1}\circ f=\iota$。显然 $\iota=\iota^{-1}$。
反转 $f$ 的自变量和因变量即得 $f^{-1}$。反转 $f^{-1}$ 的自变量和因变量即得 $f$。
交换 $f$ 的上下两行
\[f^{-1}=\begin{pmatrix}5&6&3&1&2&4\\1&2&3&4&5&6\end{pmatrix}\]稍加整理
\[f^{-1}=\begin{pmatrix}1&2&3&4&5&6\\4&5&3&6&1&2\end{pmatrix}\]定义：如果 $\mathfrak S_n$ 的子集 $G$ 满足以下三条，则称 $G$ 为 $X$ 的置换群。
- 复合封闭性，$\forall f,g\in G,f\circ g\in G$；
- 单位元，$\iota\in G$；
- 逆元封闭性，$\forall f\in G,f^{-1}\in G$。
置换群满足消去律
\[f\circ g=f\circ h\implies g=h\]证明：
\[\begin{aligned} f\circ g&=f\circ h\\ f^{-1}\circ(f\circ g)&=f^{-1}\circ(f\circ h)\\ (f^{-1}\circ f)\circ g&=(f^{-1}\circ f)\circ h\\ \iota\circ g&=\iota\circ h\\ g&=h \end{aligned}\]■
$\rho_n$ 表示 $X$ 中，$\iota$ 向「右」循环位移一位的置换
\[\rho_n(t)=t\bmod n+1\\ \rho_n=\begin{pmatrix}1&2&3&\cdots&n-1&n\\2&3&4&\cdots&n&1\end{pmatrix}\\ \rho_n^k(t)=(t-1+k)\bmod n+1,k\in[0,n-1]\cap\mathbb Z\\ \rho_n^k=\begin{pmatrix}1&2&\cdots&n-k&n-k+1&\cdots&n\\k+1&k+2&\cdots&n&1&\cdots&k\end{pmatrix}\]当 $r=k\pmod n$ 时，有 $\rho_n^r=\rho_n^k$，因此只有 $\rho_n$ 的 $n$ 种幂，分别为
\[\rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1}\]并且
\[\rho_n^{-1}=\rho_n^{n-1}\]更一般的
\[(\rho_n^k)^{-1}=\rho_n^{n-k},k\in[0,n-1]\cap\mathbb Z\]可以证明
\[C_n=\{ \rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1} \}\]是 $X$ 的置换群。
置换是一种变换，如果把 $\rho_n$ 看成多边形 $360°/n$ 旋转，那么 $\rho_n^k$ 就是 $k(360°/n)$ 旋转。如何理解？
不妨有四边形 $\text{ABCD}$，其中 $\text A$ 在第 $1$ 个点，$\text B$ 在第 $2$ 个点，$\text C$ 在第 $3$ 个点，$\text D$ 在第 $4$ 个点。记边 $\text{AB}$ 为 $a$，边 $\text{BC}$ 为 $b$，边 $\text{BC}$ 为 $c$，边 $\text{CD}$ 为 $d$。
那么四个旋转分别为
\[\begin{aligned} \rho_4^0=\iota&=\begin{pmatrix}1&2&3&4\\1&2&3&4\end{pmatrix}\\ \rho_4^1&=\begin{pmatrix}1&2&3&4\\2&3&4&1\end{pmatrix}\\ \rho_4^2&=\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}\\ \rho_4^3&=\begin{pmatrix}1&2&3&4\\4&1&2&3\end{pmatrix} \end{aligned}\]除了（沿着中心）旋转置换，还有一种常见的置换是（沿着某条对称轴）翻转
\[\tau_1=\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}\\ \tau_2=\begin{pmatrix}1&2&3&4\\3&2&1&4\end{pmatrix}\\ \tau_3=\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}\\ \tau_4=\begin{pmatrix}1&2&3&4\\4&3&2&1\end{pmatrix}\]其中 $\tau_1$ 是以顶点 $1,3$ 为对称轴的对称，$\tau_2$ 是以顶点 $2,4$ 为对称轴的对称，$\tau_3$ 是以边 $a,c$ 中点连线为对称轴的对称，$\tau_4$ 是以边 $b,d$ 中点连线为对称轴的对称。
可以证明，以上 $8$ 种置换构成了置换群 $G_4$。
如果 $X=[n]$，那么就有 $n$ 种旋转置换和 $n$ 种对称置换，我们把这 $2n$ 种置换组成的集合记作置换群 $G_n$。
如果 $n$ 为偶数，那么 $n$ 种对称置换有 $n/2$ 种是以顶点连线为对称轴的，$n/2$ 种是以边的中点连线为对称轴的对称。
当 $n$ 为奇数时，$n$ 种对称置换则均是以某顶点和其对称轴中点连线为对称轴的对称。
以下列出 $n=5$ 时的 $10$ 种置换
其中置换 $\tau_i$ 是以第 $i$ 个点和其对边的中点为对称轴的对称。
$\text{Burnside}$ 定理
令 $\mathbf c$ 为 $X$ 的一种着色，即 $i$ 的颜色是 $c(i)$。
令
为 $X$ 上的置换。
定义 $f\ast\mathbf c$ 为使得 $i_k$ 具有颜色 $c(k)$ 的着色，即
可以证明 $\ast$ 具有类似结合律的性质，也就是说 $(g\circ f)\ast\mathbf c=g\ast(f\ast\mathbf c)$ 恒成立。
举个例子，如果在正方形上每个点可以染红色或者蓝色，按 $1,2,3,4$ 的顺序列举顶点的颜色。
例如着色 $\mathbf c=(R,B,B,R)$ 就指顶点 $1,2,3,4$ 的颜色分别为红蓝蓝红。
如果着色 $\mathbf c$ 加以 $\rho_4$ 就把着色循环「右」移一位，变成 $(R,R,B,B)$。
如果着色 $\mathbf c$ 加以 $\tau_3$ 就相当于 $1,2$ 相互对称，$3,4$ 相互对称，变成 $(B,R,R,B)$。
如果着色 $\mathbf c$ 加以 $\tau_4$ 就相当于 $1,4$ 相互对称，$2,3$ 相互对称，变成 $(R,B,B,R)$。
可以看出 $\mathbf c$ 加以 $\tau_4$ 后并没有改变着色。
| $G_4$ 中的置换 | 作用于 $(R,B,B,R)$ 的效果 |
|---|---|
| $\rho_4^0=\iota$ | $(R,B,B,R)$ |
| $\rho_4^1$ | $(R,R,B,B)$ |
| $\rho_4^1$ | $(B,R,R,B)$ |
| $\rho_4^1$ | $(B,B,R,R)$ |
| $\tau_1$ | $(R,R,B,B)$ |
| $\tau_2$ | $(B,B,R,R)$ |
| $\tau_3$ | $(B,R,R,B)$ |
| $\tau_4$ | $(R,B,B,R)$ |
定义：着色集 $\mathcal C$ 是满足封闭性的集合，即
- $\forall f\in G,\forall\mathbf c\in\mathcal C,f\ast\mathbf c\in\mathcal C$
$\mathcal C$ 的定义依赖于置换群 $G$，但我们的记号里并没有显示出来，因为一般情况下这不会引起误解。
称两种染色 $\mathbf{c_1}\sim\mathbf{c_2}$，当且仅当存在 $f\in G,f\ast\mathbf{c_1}=\mathbf{c_2}$。
经典的，我们可以得出 $\sim$ 的几个性质
- 自反性，$\forall\mathbf c\in\mathcal C,\mathbf c\sim\mathbf c$；
- 对称性，$\mathbf{c_1}\sim\mathbf{c_2}\implies\mathbf{c_2}\sim\mathbf{c_1}$；
- 传递性，$\mathbf{c_1}\sim\mathbf{c_2},\mathbf{c_2}\sim\mathbf{c_3}\implies\mathbf{c_1}\sim\mathbf{c_3}$。
$\sim$ 的定义依赖于置换群 $G$，但我们的记号里并没有显示出来，因为一般情况下这不会引起误解。
令 $G$ 是 $X=[n]$ 的置换群，$\mathcal C$ 是 $X$ 的着色集，且 $\mathcal C$ 的定义依赖于置换群 $G$。
定义 $G(\mathbf c)$ 表示所有置换 $f$，满足 $f\ast\mathbf c=\mathbf c$ 组成的集合，即
\[G(\mathbf c)=\{f:f\in G,f\ast\mathbf c=\mathbf c\}\]我们称 $G(\mathbf c)$ 为着色 $\mathbf c$ 的稳定核。
定义 $\mathcal C(f)$ 表示所有着色 $\mathbf c$，满足 $f\ast\mathbf c=\mathbf c$ 组成的集合，即
\[\mathcal C(f)=\{\mathbf c:\mathbf c\in\mathcal C,f\ast\mathbf c=\mathbf c\}\]可以证明任意着色的稳定核是个置换群。
定理 $2.1$：$g\ast\mathbf c=f\ast\mathbf c$ 当且仅当 $f^{-1}\circ g\in G(\mathbf c)$。
证明：可以同乘 $f^{-1}$，再使用结合律证明左推右。倒着写就是右推左。
■
推论 $2.2$：与 $\mathbf c$ 等价的着色数等于 $G$ 中的置换个数除以 $\mathbf c$ 的稳定核中的置换个数，即
\[\vert\{f\ast\mathbf c:f\in G\}\vert=\frac{\vert G\vert}{\vert G(\mathbf c)\vert}\]证明：由定理 $2.1$，$g\ast\mathbf c=f\ast\mathbf c\iff f^{-1}\circ g\in G(\mathbf c)\iff g\in{f\circ h:h\in G(\mathbf c)}$。
记集合 $s={f\circ h:h\in G(\mathbf c)}$，取 $h_1,h_2\in s$，记 $g_1=f\circ h_1$，$g_2=f\circ h_2$。
根据 $G(\mathbf c)$ 的定义，$h_1\ast\mathbf c=h_2\ast\mathbf c\implies f\circ h_1\ast\mathbf c=f\circ h_2\ast\mathbf c\implies g_1\ast\mathbf c=g_2\ast\mathbf c$。
因为 $g$ 互不相同，所以对于每个置换 $f$，恰好存在 $\vert G(\mathbf c)\vert$ 个置换，这 $\vert G(\mathbf c)\vert$ 个置换作用在 $\mathbf c$ 上有相同的效果。
所以将 $\vert G\vert$ 除以 $\vert G(\mathbf c)\vert$ 即证。
■
定理 $2.3$（$\text{Burnside}$ 定理）：$\mathcal C$ 中非等价着色数 $N(G,\mathcal C)$ 由下式给出
\[N(G,\mathcal C)=\frac1{\vert G\vert}\sum_{f\in G}\vert\mathcal C(f)\vert\]考虑计数如下二元组 $(f,\mathbf c)$ 的数量，满足 $f\ast\mathbf c=\mathbf c$，那么
\[\sum_{f\in G}\vert\mathcal C(f)\vert=\sum_{\mathbf c\in\mathcal C}\vert G(\mathbf c)\vert\]由推论 $2.1$ 可得
\[\vert G(\mathbf c)\vert=\frac{\vert G\vert}{\#[与 \mathbf c 等价的着色数]}\]因此
\[\sum_{\mathbf c\in\mathcal C}\vert G(\mathbf c)\vert=\vert G\vert\sum_{\mathbf c\in\mathcal C}\frac1{\#[与 \mathbf c 等价的着色数]}\]如果有 $k$ 种着色等价，那么每种着色的贡献都是 $1/k$，也就是说每种本质不同的着色数的贡献均为 $1$。因此
\[\sum_{\mathbf c\in\mathcal C}\frac1{\#[与 \mathbf c 等价的着色数]}=N(G,\mathcal C)\]联立上述两式稍加整理，即证。
■
将 $n$ 个人排成一个圆桌，求方案数。
断环为链，钦定一个「桌头」，那么方案数是 $(n-1)!$。
如果用群的角度来解决这题，那么有置换群 $C_n={ \rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1} }$。
由于每个人互不相同，只有置换 $\iota$ 能满足 $\mathcal C(\iota)$ 非空。因此
将 $n$ 颗不同的宝石排成项链，求方案数。
和刚刚那题的区别是项链可以沿着对称轴翻转，但圆桌不行。
有置换群 $G_n={ \rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1},\tau_1,\tau_2,\cdots,\tau_n }$。
但和刚刚一样只有 $\iota$ 有贡献，因此
用 $p$ 种不同颜色对五边形顶点进行着色，求方案数。
可以把置换群分成 $3$ 类：
- $\iota$，任意染色方案在 $\iota$ 下均不变，因此贡献为 $p^5$；
- $\rho_5^1,\rho_5^2,\rho_5^3,\rho_5^4$，当且仅当所有顶点颜色相同时旋转，着色方案才不变，因此贡献为 $4\times p$；
- $\tau_1,\tau_2,\tau_3,\tau_4,\tau_5$，其中第 $i$ 个点颜色任意，其余有 $2$ 组对称点，只要保证每组对称点颜色相同即可，因此贡献为 $2\times(1+p^2)$
用 $p$ 种不同颜色对长度为 $n$ 的序列进行染色，若从左到右的顺序和从有到做的顺序视为相同的染色方案，求方案数。
这里
\[G=\{\iota,\tau\}\\ \iota=\begin{pmatrix}1&2&\cdots&n-1&n\\1&2&\cdots&n-1&n\end{pmatrix}\\ \tau=\begin{pmatrix}1&2&\cdots&n-1&n\\n&n-1&\cdots&2&1\end{pmatrix}\]对于 $\iota$，其贡献为 $p^n$。
对于 $\tau$，我们必须对奇偶进行分类讨论。
- 如果 $n$ 为偶数，形成了 $n/2$ 组对称，所以其贡献为 $p^{n/2}$；
- 如果 $n$ 为奇数，只有第 $(n+1)/2$ 个点的颜色可以任意选取，其余形成了 $(n-1)/2$ 组对称，所以其贡献为 $p\times p^{(n-1)/2}$。
如果采取下取整符号，那么 $\tau$ 的贡献为 $p^{\lfloor(n+1)/2\rfloor}$。
\[N(G,\mathcal C)=\frac12(p^n+p^{\lfloor(n+1)/2\rfloor})\]$\text{Pólya}$ 定理
鉴由上述题目，我们发现在 $p$ 种颜色下，只需要知道某置换的置换环数量为 $m$，即可知道这个置换环的贡献为 $p^m$。
如果你对置换环还不了解，那可以看看下面的解释。
我们知道置换 $f$ 可以用 $k\to f(i_k)$ 的有向边进行解释。一个置换有 $n$ 条这样的有向边。
由置换的定义可知，每个点的入度和出度均为 $1$。因此这 $n$ 条有向边组成了一个有向环森林。
我们可以把一个置换分解为若干置换环，比如
$f\ast\mathbf c$ 相当于把 $1$ 的颜色给了 $6$，把 $6$ 的颜色给了 $3$，把 $3$ 的颜色给了 $5$，把 $5$ 的颜色给了 $1$；把 $2$ 的颜色给了 $8$，把 $8$ 的颜色给了 $7$，把 $7$ 的颜色给了 $2$；把 $4$ 的颜色给了 $4$。
为了在加以置换 $f$ 后着色相同，必须使相同置换环的颜色相同。$3$ 个置换环意味着其贡献为 $p^3$。
定理 $3.1$：若有 $k$ 种颜色对 $X$ 进行染色，$\mathcal C$ 为着色集，置换 $f$ 下保持不变的着色数为
\[\vert\mathcal C(f)\vert=k^m\]其中 $m$ 为置换 $f$ 的置换环数量。
下面给出 $G_4$ 的置换环，便于读者理解。
| $G_4$ 中的置换 | 置换环分解 | 置换环数量 | $\mathcal C(f)$ |
|---|---|---|---|
| $\rho_4^0=\iota$ | $\begin{bmatrix}1\end{bmatrix}\circ\begin{bmatrix}2\end{bmatrix}\circ\begin{bmatrix}3\end{bmatrix}\circ\begin{bmatrix}4\end{bmatrix}$ | $4$ | $p^4$ |
| $\rho_4^1$ | $\begin{bmatrix}1&2&3&4\end{bmatrix}$ | $1$ | $p^1$ |
| $\rho_4^2$ | $\begin{bmatrix}1&3\end{bmatrix}\circ\begin{bmatrix}2&4\end{bmatrix}$ | $2$ | $p^2$ |
| $\rho_4^3$ | $\begin{bmatrix}1&4&3&2\end{bmatrix}$ | $1$ | $p^1$ |
| $\tau_1$ | $\begin{bmatrix}1\end{bmatrix}\circ\begin{bmatrix}2&4\end{bmatrix}\circ\begin{bmatrix}3\end{bmatrix}$ | $3$ | $p^3$ |
| $\tau_2$ | $\begin{bmatrix}1&3\end{bmatrix}\circ\begin{bmatrix}2\end{bmatrix}\circ\begin{bmatrix}4\end{bmatrix}$ | $3$ | $p^3$ |
| $\tau_3$ | $\begin{bmatrix}1&2\end{bmatrix}\circ\begin{bmatrix}3&4\end{bmatrix}$ | $2$ | $p^2$ |
| $\tau_4$ | $\begin{bmatrix}1&4\end{bmatrix}\circ\begin{bmatrix}2&3\end{bmatrix}$ | $2$ | $p^2$ |
由此可以看出
\[N(G,\mathcal C)=\frac18(p^4+p^1+p^2+p^1+p^3+p^3+p^2+p^2)=\frac{p^4+2p^3+3p^2+2p}8\]记置换 $f$ 中，长度为 $i$ 的置换环数量为 $e_i$。
假如用 $v_1,v_2,\cdots,v_p$ 代表第 $1,2,\cdots,p$ 种颜色。
这里 $v_1,v_2,\cdots,v_p$ 是 $p$ 元生成函数的变量，只是一个符号。
记 $z_i=v_1^i+v_2^i+\cdots+v_p^i$。
定理 $3.2$（$\text{Pólya}$ 定理，以生成函数的形式给出）：
\[N(G,\mathcal C,m_1,m_2,\cdots,m_p)=[v_1^{m_1}v_2^{m_2}\cdots v_p^{m_p}]\frac1{\vert G\vert}\sum_{f\in G}z_1^{e_1}z_2^{e_2}\cdots z_n^{e_n}\]其中 $N(G,\mathcal C,m_1,m_2,\cdots,m_p)$ 表示第 $k$ 种颜色恰用了 $m_k$ 种的方案数。
当取 $v_1=v_2=\cdots=v_p=1$ 时，$z_i=p$，此时系数和就是 $N(G,\mathcal C)$，相当于回到了 $\text{Burnside}$ 定理。
举个例子，当 $p=2$ 时，令 $r=v_1,b=v_2$，那么
| $G_4$ 中的置换 | 置换环分解 | $(e_1,e_2,e_3,e_4)$ | $z_1^{e_1}z_2^{e_2}z_3^{e_3}z_4^{e_4}$ |
|---|---|---|---|
| $\rho_4^0=\iota$ | $\begin{bmatrix}1\end{bmatrix}\circ\begin{bmatrix}2\end{bmatrix}\circ\begin{bmatrix}3\end{bmatrix}\circ\begin{bmatrix}4\end{bmatrix}$ | $(4,0,0,0)$ | $z_1^4z_2^0z_3^0z_4^0=z_1^4$ |
| $\rho_4^1$ | $\begin{bmatrix}1&2&3&4\end{bmatrix}$ | $(0,0,0,1)$ | $z_1^0z_2^0z_3^0z_4^1=z_4$ |
| $\rho_4^2$ | $\begin{bmatrix}1&3\end{bmatrix}\circ\begin{bmatrix}2&4\end{bmatrix}$ | $(0,2,0,0)$ | $z_1^0z_2^2z_3^0z_4^0=z_2^2$ |
| $\rho_4^3$ | $\begin{bmatrix}1&4&3&2\end{bmatrix}$ | $(0,0,0,1)$ | $z_0^0z_2^0z_3^0z_4^1=z_4$ |
| $\tau_1$ | $\begin{bmatrix}1\end{bmatrix}\circ\begin{bmatrix}2&4\end{bmatrix}\circ\begin{bmatrix}3\end{bmatrix}$ | $(2,1,0,0)$ | $z_1^2z_2^1z_3^0z_4^0=z_1^2z_2$ |
| $\tau_2$ | $\begin{bmatrix}1&3\end{bmatrix}\circ\begin{bmatrix}2\end{bmatrix}\circ\begin{bmatrix}4\end{bmatrix}$ | $(2,1,0,0)$ | $z_1^2z_2^1z_3^0z_4^0=z_1^2z_2$ |
| $\tau_3$ | $\begin{bmatrix}1&2\end{bmatrix}\circ\begin{bmatrix}3&4\end{bmatrix}$ | $(0,2,0,0)$ | $z_1^0z_2^2z_3^0z_4^0=z_2^2$ |
| $\tau_4$ | $\begin{bmatrix}1&4\end{bmatrix}\circ\begin{bmatrix}2&3\end{bmatrix}$ | $(0,2,0,0)$ | $z_1^0z_2^2z_3^0z_4^0=z_2^2$ |
因此 $4R$ 的方案数为 $1$，$3R1B$ 的方案数为 $1$，$2R2B$ 的方案数为 $2$，$1R3B$ 的方案数为 $1$，$4B$ 的方案数为 $1$，总方案数为 $6$。
LGP4980 【模板】Polya 定理：给定一个 $n$ 个点，$n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模。
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
这里明确 $C_n={ \rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1} }$ 后，难点在于 $\vert\mathcal C(\rho_n^k)\vert$ 的值如何计算。
进行置换 $\rho_n^k$ 后，如果不考虑循环，那么原先在位置 $i$ 的转移到了 $i+k$，原先在位置 $i+k$ 的转移到了 $i+2k$。
我们要求出 $\rho_n^k$ 的置换环长度。只需求最小的正整数 $x$，满足 $kx=0\pmod n$，那么置换环的长度为 $x$。另外我们还能知道总共有 $n/x$ 个这样的置换环。
运用 $\text{exgcd}$ 的知识，我们知道 $x=n/\gcd(n,k)$，并且有 $\gcd(n,k)$ 个这样的置换环。
这个式子是 $\mathcal O(n)$ 的，我们需要枚举 $\gcd$ 来获得更低的复杂度。
\[\begin{aligned} N(G,\mathcal C)&=\frac1n\sum_{k=0}^{n-1}p^{\gcd(n,k)}\\ &=\frac1n\sum_{d\vert n}\sum_{i=1}^n[\gcd(n,i)=d]p^d\\ &=\frac1n\sum_{d\vert n}p^d\sum_{i=1}^n[\gcd(n,i)=d]\\ &=\frac1n\sum_{d\vert n}p^d\sum_{d\vert i}[\gcd(\frac nd,\frac id)=1]\\ &=\frac1n\sum_{d\vert n}p^d\varphi(\frac nd) \end{aligned}\]那要是考虑对称置换怎么办？
置换群 $G_n={ \rho_n^0=\iota,\rho_n^1,\rho_n^2,\cdots,\rho_n^{n-1},\tau_1,\tau_2,\cdots,\tau_n }$，对于 $\rho_n^k$ 的情况我们已经考虑清楚了。
再次奇偶讨论：
- 如果 $n$ 为偶数，形成了 $n/2$ 组对称，所以其贡献为 $p^{n/2}$；
- 如果 $n$ 为奇数，只有第 $(n+1)/2$ 个点的颜色可以任意选取，其余形成了 $(n-1)/2$ 组对称，所以其贡献为 $p\times p^{(n-1)/2}$。
如果采取下取整符号，那么 $\tau$ 的贡献为 $n\times p^{\lfloor(n+1)/2\rfloor}$，于是
\[N(G,\mathcal C)=\frac1{2n}(\sum_{d\vert n}p^d\varphi(\frac nd)+np^{\lfloor(n+1)/2\rfloor})\]LGP4128 [SHOI2006] 有色图：如果一张无向完全图（完全图就是任意两个不同的顶点之间有且仅有一条边相连）的每条边都被染成了一种颜色，我们就称这种图为有色图。如果两张有色图有相同数量的顶点，而且经过某种顶点编号的重排，能够使得两张图对应的边的颜色是一样的，我们就称这两张有色图是同构的。以下两张图就是同构的，因为假如你把第一张图的顶点 $(1,2,3,4)$ 置换成第二张图的 $(4,3,2,1)$，就会发现它们是一样的。
你的任务是，对于计算所有顶点数为 $n$，颜色种类不超过 $m$ 的图，最多有几张是两两不同构的图。由于最后的答案会很大，你只要输出结论模 $p$ 的余数就可以了（$p$ 是一个质数）。
对于 $100 \%$ 的数据，$1\leq n\leq 53$，$1\leq m\leq 1000$，$n<p\leq 10^9$。
我们先把 $n$ 拆成 $k$ 个正整数，$a_i$ 表示第 $i$ 点个置换环的长度，且满足 $a_1\le a_2\le\cdots\le a_k$，同时 $\sum a_i=n$。
拆解部分可以使用 $\text{dfs}$ 来实现。由于 $53$ 的拆分数不太大，故不会超时。
但是题目中染色的东西是边，即对于置换 $f$，边 $(x,y)$ 实际上被置换为了 $(f(x),f(y))$，而我们要求的置换环数量实际上是 $(f(x),f(y))$ 这 $\binom n2$ 个边构成的置换环数量。
由于边的置换是依赖于点的置换的，所以置换群的大小照常计算，$\vert G\vert=n!$。
对于所有边，按照两个点是否在同一个置换环内去考虑：
- 如果在同一个点置换环内，按照 $x,y$ 之间的距离进行分类，可以发现 $x,y$ 距离相等的边形成了边置换环，稍加讨论发现不论 $a_i$ 的奇偶性，大小为 $a_i$ 的点置换环 $i$ 自身可以产生 $\lfloor a_i/2\rfloor$ 个边置换环。
- 如果不在同一个点置换环内，具体地，$x$ 在长度为 $a_i$ 的点置换环内，$y$ 在长度为 $a_j$ 的置换环内，那一条边走 $\operatorname{lcm}(a_i,a_j)$ 才能回到原位。因此点置换环 $i,j$ 产生的边置换环数量为 $a_ia_j/\operatorname{lcm}(a_i,a_j)=\gcd(a_i,a_j)$。
因此总置换环数即为
\[\sum_{i=1}^n\left\lfloor\frac{a_i}2\right\rfloor+\sum_{i<j}\gcd(a_i,a_j)\]这题还有一个棘手之处在于我们分解出来的 $a_i$ 出现了几次？
是多项式系数再除去相同的顺序，即
其中 $c_k=\sum\limits_{i=1}^n[a_i=k]$，即 $k$ 在 $a$ 中的出现次数。
\[\begin{aligned} N(G,\mathcal C)&=\frac1{n!}\sum_a\frac{n!}{\prod\limits_{i=1}^na_i!\times\prod\limits_{i=1}^nc_i!}k^{\sum_{i=1}^n\left\lfloor\frac{a_i}2\right\rfloor+\sum_{i<j}\gcd(a_i,a_j)}\\ &=\sum_a\frac1{\prod\limits_{i=1}^na_i!\times\prod\limits_{i=1}^nc_i!}k^{\sum_{i=1}^n\left\lfloor\frac{a_i}2\right\rfloor+\sum_{i<j}\gcd(a_i,a_j)}\\ \end{aligned}\]