Pólya 定理学习笔记
Vocalise
·
·
题解
Pólya 定理在计数方面可以统计「本质不同」的方案个数。
下面从群论的基础开始讲起。
感谢 @Soulist
群
定义一个集合与作用在其上的二元运算 (G,\times)，若其具有：
- 封闭性：对于 a,b\in G，a\times b\in G。
- 结合律：对于 a,b,c\in G，(a\times b)\times c = a\times(b\times c)。
- 单位元：记为 e，对于 a\in G，a\times e = e\times a = a。
- 逆元：对于 a\in G，存在唯一的逆元记为 a^{-1}\in G，使 a\times a^{-1} = a^{-1}\times a = e。
下文中「群的运算」都记为通常的乘法标记 \times。
一些性质/定义
群的阶: 群中元素的个数。记作 |T|.
子群
下文中沿用 $T$ 是 $G$ 的子群讨论一些性质/定理。
### 陪集
对于任意 $g\in G$，记 $gT$ 为 $G$ 的一个左陪集，表示 $\forall h\in T$ 变为 $g\times h$。$Tg$ 称为右陪集，表示 $\forall h$ 变为 $h\times g$。
下文只讨论左陪集。
$G/T$ 表示 $G$ 中所有 $T$ 的左陪集；
$[G:T]$ 表示 $G$ 中所有 $T$ 的左陪集数量，即 $\left|G/T\right|$。
有重要的性质：$g\in T$ 与 $gT = T$ 等价。由封闭性易得。
### 群作用
分为左群作用和右群作用，下面讨论左群。
对于集合 $S$ 的任意元素 $a$，若对于群 $G$ 的元素 $v,u$ 和单位元 $e$ 有映射 $G\times S\to S$ 记作二元运算 $\circ$，使得
$$ e\circ a = a $$
$$ (v\times u)\circ a = v\circ (u\circ a) $$
则称 $G$ 作用在 $S$ 上。下文沿用 $\circ$ 记号。
一般的理解就是群的作用效果可以以一定方式推广到一个集合上，虽然该集合不一定具备群的性质。
下文中会有例子，如：一个有标号环从某个点开始的标号序列与旋转该环操作构成的群，作用在每个点的颜色构成的序列上。
### 置换群
**置换**是「映射」的一种，是指非空集到它本身的**双射**。
经常讨论的是集合 $S = \{a_1,a_2,\cdots,a_n\}$ 上的置换群。
对于该集合，最大的置换群是 $n$ **元对称群**，其阶为 $n!$，可理解为全排列。所有 $n$ 元置换群都是它的子群。
一个置换一般写作：
$$g = \begin{pmatrix}a_1,a_2,\cdots,a_n\\a_{p1},a_{p2},\cdots,a_{pn}\end{pmatrix}$$
如默认上一行是 $(a_1,a_2,\cdots,a_n)$，则也许会省略掉。
有定理：一个 $n$ 元置换可以表示为若干循环循环置换的置换的乘积。顺序选取若干元素 $(a_{p1},a_{p2},\cdots,a_{pn})$，它们的循环置换是：
$$\begin{pmatrix}
a_{p1},a_{p2},\cdots,a_{pn}\\
a_{p2},a_{p3},\cdots,a_{p1}
\end{pmatrix}$$
该定理也比较显然。把每个置换看作一条有向边，$n$ 个点的图中每个点都有一条出边，形成的图由多个环组成。一个置换的**轮换**就是图上环的集合。
## 拉格朗日定理
若 $T$ 是 $G$ 的子群，则
$$ |T|\times [G:T] = |G| $$
证明：首先有 $g\in G$，则 $|gT| = |T|$。
比较显然：已知 $T$ 的元素到 $gT$ 的元素有一个映射，则 $|gT|\le |T|$；如果 $|gT| < |T|$，则一定会有 $v,u\in T,v\not=u$，$g\times v = g\times u$，发现 $g$ 是可乘上 $g^{-1}$ 消去的，则不存在这样的 $v,u$。
然后有 $\forall g_1,g_2\in G$，$g_1T\cap g_2T=\varnothing$ 或 $g_1T = g_2T$。
设 $g_1T\cap g_2T$ 中有元素 $v$，则 $g_1^{-1}\times v,g_2^{-1}\times v\in T$，$g_1^{-1}\times v\times(g_2^{-1}\times v)^{-1}=g_1^{-1}\times v\times v^{-1}\times g_2 = g_1^{-1}\times g_2\in T$。
结合陪集性质，$(g_1^{-1}\times g_2)T = T$，两边同时左乘 $g_1$ 变换，得到 $g_1T = g_2T$。
如果不存在 $v$，则无上述过程。
因此可知：$T$ 在 $G$ 中每个本质不同的陪集阶都为 $|T|$，且互不相交。显然这些陪集的并就是 $G$（因为仅单位元 $e$ 左乘所有元素就可以得到 $G$ 的所有元素），所以拉格朗日定理得证。
## 轨道-稳定子定理
下文中讨论的群 $T$ 作用在集合 $S$ 上，$x\in S$。
记 $T^x$ 为 $T$ 中作用于 $x$ 上使它没有变化的元素集合。该集合称为 $x$ 的**稳定子**。
记 $T(x)$ 为 $T$ 中所有元素作用在 $x$ 上得到的集合。该集合称为 $x$ 的**轨道**。
轨道-稳定子定理指出：
$$|T^x|\times |T(x)| = |T|$$
对任意 $x\in S$ 都成立。
证明：首先证明 $T^x$ 是 $T$ 的子群，然后运用拉格朗日定理。
$T^x$ 的元素显然都属于 $T$，下面指出它具有群的性质。
1. 封闭性：对于 $a,b\in T^x$，$a\circ x = b\circ x = x$，则群作用的性质 $(a\times b)\circ x = x$，得到 $a\times b\in T^x$，得证。
2. 结合律：显然。
3. 单位元：显然 $T$ 的单位元 $e$ 有 $e\circ x = x$，$e\in T^x$。
4. 逆元：由于 $e\in T^x$，对于 $a\in T^x$ 有 $e\circ x = (a^{-1}\times a)\circ x = a^{-1}\circ(a\circ x) = x$，取 $T$ 中的逆元即可。
于是得证。
运用拉格朗日定理 $|T^x|\times[T:T^x] = |T|$，我们只需要证明 $[T:T^x] = |T(x)|$。
即：$x$ 的稳定子群陪集的个数等于其轨道的大小。
尝试建立双射关系。对于 $g\in T$，我们用 $gT^x$ 对应一个稳定子群的陪集。
对于 $f\circ x = g\circ x$，它们是轨道中的相同元素。则同时左乘 $g^{-1}$ 得到 $(g^{-1}\times f)\circ x = e\circ x$，$g^{-1}\times f\in T^x$，$(g^{-1}\times f)T^x = T^x$，$fT^x = gT^x$。
另外对于 $fT^x = gT^x$ 也有 $g^{-1}\times f\in T^x$，$f\circ x = g\circ x$。于是得证。
## Burnside 引理
定义：若 $x,y\in S$，且存在 $g\in T$ 使 $g\circ x = y$，则同样有 $g^{-1}\circ y = x$，称 $x,y$ 是本质相同的。
有记号：$S/T$ 表示在 $T$ 的作用下本质不同的每种种类元素集合的集合，即按颜色划分为若干块。
上文有记号 $T^x$ 是 $x$ 在 $T$ 作用下的稳定集合，这里类似地引入 $S^g$ 表示 $g$ 作用下 $S$ 中不改变的元素集合。
Burnside 引理指出
$$ |S/T| = \frac 1{|T|}\sum_{g\in T}|S^g| $$
发现后求和式本质和枚举 $T^x$ 是一样的，~~但是定理就是这样。~~
则
$$ |S/T| = \frac 1{|T|}\sum_{x\in S}|T^x| $$
运用轨道-稳定子定理：
$$ \begin{aligned}
&\quad\frac 1{|T|}\sum_{x\in S}T^x = \sum_{x\in S}\frac{|T^x|}{|T|} = \sum_{x\in S}\frac 1{|T(x)|} \\
&= \sum_{G\in S/T}\sum_{x\in G}\frac 1{|T(x)|}
= \sum_{G\in S/T}\sum_{x\in G}\frac 1{|G|} \\
&= \sum_{G\in S/T}1 = |S/T|
\end{aligned} $$
其核心在于每种颜色不相交，以及同种颜色中每个元素的轨道都为该颜色集合。
## Pólya 定理
Pólya 定理和 Burnside 引理类似。但我们的问题细化一些：
我们给 $S$ 中每一个元素染色，统计 $T$ 作用下本质不同的染色方案数。
已经介绍轮换的概念，记 $c(g)$ 为 $g$ 中的轮换个数，$N$ 为颜色集合。
$$ |S/T| = \frac 1{|T|}\sum_{g\in T}|N|^{c(g)} $$
对于它，我们只考虑证明 $|N|^{c(g)} = |S^g|$。
发现每个轮换等价于一个连通块（$n$ 个点 $n$ 条出边），$S^g$ 中必然是每个轮换染相同的颜色即可，每个轮换自然有 $|N|$ 种方案，也就是 $|N|^{c(g)}$ 了。
---
## [P4980 【模板】Pólya 定理](https://www.luogu.com.cn/problem/P4980)
比较单纯的问题，循环置换群作用在长度为 $n$，$n$ 种颜色的颜色序列集合上，求本质不同的方案数。
循环置换按长度有 $0\sim n-1$ 有 $n$ 个分别为 $p_0\sim p_{n-1}$。则：
$$ |S/T| = \frac 1n\sum_{i=0}^{n-1}n^{c(p_i)} $$
考虑 $c(p_i)$。
一个轮换经过了若干次全长 $n$，同时又由若干个 $i$ 步长组成，因此一个轮换的长度是 $\operatorname{lcm}(i,n)$。每个元素在且仅在一个轮换中，因此若干个轮换的总长是 $i\times n$。
得到结论：旋转 $i$ 次的轮换有 $\dfrac{i\times n}{\operatorname{lcm}(i,n)} = \gcd(i,n)$ 个。
但是 $\gcd(0,n)$ 不好处理，我们认为旋转 $0$ 次是旋转 $n$ 次，原式为：
$$ |S/T| = \frac 1n\sum_{i=1}^nn^{\gcd(n,i)} $$
求这个式子是容易的，不展开来讲。
$$ \begin{aligned}
|S/T| &= \frac 1n\sum_{d|n}n^d\sum_{i=1}^n[\gcd(n,i) = d] \\
&= \frac 1n\sum_{d|n}n^d\sum_{i=1}^{n/d}[\gcd(\frac nd,i)=1] \\
&= \frac 1n\sum_{d|n}n^d\varphi(\frac nd)
\end{aligned} $$
暴力枚举约数，$O(\sqrt n)$ 求 $\varphi$，$O(\log n)$ 求快速幂可以过。
但是显然可以筛素因子做到 $O(Td(n)\log n)\approx O(Tn^{\frac{1.066}{\ln\ln n}}\log n)$，$10^9$ 中大约是 $O(Tn^{\frac 13}\log n)$。
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
const int p = 1000000007;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9');
return x * f;
}
int fastpow(int a,int b) {
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}
int n;
int phi(int n) {
int res = n;
for(int i = 2;i * i <= n;i++) {
if(n % i) continue;
res -= res / i;
while(!(n % i)) n /= i;
}
if(n > 1) res -= res / n;
return res;
}
int f(int d) {
return 1ll * fastpow(n,d) * phi(n / d) % p;
}
void Solve() {
n = read(); int ans = 0,d;
for(d = 1;d * d < n;d++)
if(!(n % d)) {
ans = (ans + f(d)) % p;
ans = (ans + f(n / d)) % p;
}
if(d * d == n) ans = (ans + f(d)) % p;
std::printf("%lld\n",1ll * ans * fastpow(n,p - 2) % p);
return;
}
int main() {
int t = read();
while(t--) Solve();
return 0;
}
```