参考资料
- 《组合数学（第 5 版）》
- Soulist：Polya 定理。
轨道 - 稳定子定理
对 \(S_n\) 的一个子群 \(G\)，设 \(Z_k\) 表示作用在 \(1\sim n\) 上使 \(k\) 保持不动的置换类，\(E_k\) 表示 \(k\) 在群 \(G\) 作用下的 “轨道” —— 所能到达的位置集合，有 \(|E_k||Z_k| = |G|\)。i.e. 使 \(k\) 保持不动的置换个数乘以其轨道大小等于置换群大小。
证明：对于一个等价类 \(E = \{a_1, a_2, \cdots, a_{|E|}\}\)，使 \(a_1\) 不动的置换类为 \(Z_{a_1}\)。存在置换 \(p_i\) 使得 \(a_1\) 变为 \(a_i\)。设 \(G_i = Z_{a_1}p_i\)，则 \(G_i\) 互不相交（对 \(a_1\) 产生的影响不同），且大小均为 \(|Z_{a_1}|\)。又因为 \(G_i\) 的并包含于 \(G\)，且任何属于 \(G\) 的元素均属于 \(G_i\) 的并，故 \(\sum |G_i| = |G|\)，即 \(|E_{a_1}||Z_{a_1}| = |G|\)。
换句话说，使 \(a_1\) 不动的所有置换 \(Z_{a_1}\) 在乘以使 \(a_1\) 变为其 所在等价类 的 \(a_i\) 的 任意一个 置换 \(p_i\) 后，可以得到 所有 使 \(a_1\) 变为 \(a_i\) 的置换 \(G_i\)，且大小均为 \(|Z_{a_1}|\)。
Burnside 引理
设定义在 \(G\) 上的函数 \(f(g)\ (g\in G)\) 表示使集合 \(S\) 中的元素 \(k\) 在置换 \(g\) 的作用下不变的 \(k\) 的个数，即置换的 不动点 数量。\(f(g) = \sum\limits_{k \in S} ^ S [g(k) = k]\)，则 \(G\) 作用在集合 \(S\) 上的本质不同等价类个数为 \(\dfrac{\sum\limits_{g\in G} f(g)}{|G|}\)。
- Proof. 对属于同一等价类的所有元素 \(a_i\)，据定义可知这样的 \(a_i\) 有 \(|E_{a_i}|\) 个。每个 \(a_i\) 会在 \(g\in Z_{a_i}\) 的置换处被统计，故对于总和的贡献为 \(|Z_{a_i}|\)。因此，每个 等价类 对答案的贡献为 \(|E_{a_i}||Z_{a_i}|=|G|\)。\(\square\)
Pólya 计数定理
Pólya 定理是 Burnside 引理的推广，它应用于 染色问题 的 循环同构 方案计数。设 \(c(g)\) 表示置换 \(g\) 的 循环节 个数。用 \(m\) 种颜色给 \(n\) 个对象染色在 \(n\) 阶置换群 \(G\) 意义下的方案数为 \(\dfrac {\sum\limits_{g\in G}m ^ {c(g)}} {|G|}\)。
- Proof. 由 Burnside 引理，只需证明 \(f(g)=m^{c(g)}\)。若一组染色方案 \(c_1, c_2, \cdots, c_n(c_i\in [1, m])\) 在置换 \(g\) 下是不动点，则对于 \(g\) 的任意循环 \((p_1, p_2, \cdots, p_i)\) 均有 \(c_{p_1} = c_{p_2} = \cdots = c_{p_i}\)。每个循环有 \(m\) 种染色方式，因此总方案数即不动点数量，由乘法原理得 \(m^{c(g)}\)。\(\square\)
Pólya 定理在 OI 界的运用
- 仅考虑 循环同构 的式子形如 \(\dfrac{\sum\limits_{i = 1} ^ n m ^ {\gcd(n, i)}} n\)。\(n\) 在模意义下可能没有逆元，此时可扩展数域，将每个数写成 \(an+b\) 的形式。乘法法则形如 \((an + b)(cn + d) = (acn + ad + bc)n + bd\)。最后取出 \(n\) 前面的系数即可。注意，求完整个 \(\sum\) 才能忽略 \(b\)。
I. P4980 【模板】Pólya 定理
Pólya 定理的简单应用。一个 \(n\sim k\) 阶旋转置换（共有 \(n\) 个元素，每个元素旋转 \(k\) 单位） 的循环节个数为 \(\gcd(n, k)\)，故答案为 \(\dfrac{\sum\limits_{i = 1} ^ n n ^ {\gcd(i, n)}} n\)。因为 \(d\mid \gcd(i, n)\)，考虑枚举 \(d\mid n\)，原式等于 \(\dfrac 1 n \sum\limits_{d\mid n} n ^ d\sum\limits_{i = 1} ^ n[\gcd(i, n) = d]\) 即 \(\dfrac 1 n\sum\limits_{d\mid n}n ^ d \varphi\left(\dfrac n d\right)\)。枚举所有因数并暴力，或先筛出所有素数求欧拉函数。时间复杂度 \(\mathcal{O}(Td(n)\sqrt n)\)。常数非常小，可以通过。
*II. P5233 [JSOI2012]爱之项链
本题和 Pólya 定理的板子非常相似。问题分为两部分：求单独一个环形的方案数，以及给 \(n\) 阶环相邻元素染不同颜色的方案数。前者是板子，后者是经典问题。
*III. CF1630E Expected Components
高妙计数题。考虑将问题分为两部分来做：一是求方案数，二是求总连通块数量。
性质 1：我们并不关心数字的值，仅关心每个数字的出现次数 \(cnt\)。因此，设不同的数共有 \(c\) 个，大小分别为 \(1\sim c\)，出现次数分别为 \(cnt_1, cnt_2, \cdots, cnt_c\)。
求方案数：循环同构自然想到 Burnside 引理。我们需要求出在旋转 \(k\ (1\leq k\leq n)\) 个单位下不动点的数量。
我们知道，旋转 \(k\) 单位的置换 \(g_k\) 会将大小为 \(n\) 的循环队列分成 \(\gcd(n, k)\) 个大小为 \(\dfrac n {\gcd(n, k)}\) 的等价类，每个等价类内部所有数应相等，才能保证它在置换 \(g_k\) 下 不动。例如当 \(k = 2\)，\(n = 6\) 时，只有 \(a_1 = a_3 = a_5\) 且 \(a_2 = a_4 = a_6\) 时它是 \(g_2\) 的不动点，故只需要确定 \(a_1, a_2\) 即可确定整个序列。换句话说，\(a_1 \sim a_{\gcd(n, k)}\) 是 自由变量，\(g_k\) 把循环队列的大小从 \(n\) 缩成了 \(\gcd(n, k)\)。
考虑枚举 \(k\)，令 \(L = \gcd(n, k)\)，\(d = \dfrac n L\)，则相当于我们将问题规模缩小了 \(d\) 倍：因为 \(a_1 \sim a_L\) 是自由变量，而 \(a_i\ (L < i \leq n)\) 依赖于 \(a_{i - L}\) 的取值（必须与 \(a_{i - L}\) 相等），这样才能保证 \(a\) 在置换 \(g_k\) 下不动。
因此，总方案数即 \(\dbinom {L}{\frac {cnt_1} d, \frac {cnt_2} d, \cdots, \frac {cnt_c} d}\) 表示往 \(L\) 个位置分别放入 \(\dfrac {cnt_i} d\) 个相同的数，这是经典的多重组合数。
直接枚举 \(k\)，时间复杂度平方，无法接受。但注意到很多 \(k\) 均无解：对应算出的 \(d\) 不整除于某个 \(cnt\)。此时我们无法将问题规模缩小 \(d\) 倍，即 \(g_k\) 不存在不动点。另有很多 \(k\) 和 \(n\) 的 \(\gcd\) 相等，说明我们进行了很多次重复计算。
容易发现 \(d\) 应当满足 \(d\mid \gcd(cnt_i, n)\)，故直接枚举 \(\gcd(cnt_i, n)\) 的因数 \(d\)，算出 \(L\) 以及对应的多重组合数，记为 \(f_L\)，表示长为 \(L\) 的循环队列的答案。总方案数即
\]
类似的，对于连通块数量，由于任意两个相邻的不同的数均会产生 \(1\) 的贡献，故直接枚举这两个数 \(x, y\ (x\neq y)\)。总方案数为 \(g_L = \dbinom {L - 2}{\frac {cnt_1} d, \frac {cnt_2} d, \cdots , \frac {cnt_x} d - 1, \cdots , \frac {cnt_y} d - 1, \frac {cnt_c} d}\times n\)，这是因为我们钦定了某两个相邻元素分别为 \(x, y\)，贡献即剩下来的所有数的排列方案数，乘以可能产生贡献的所有位置数量。注意乘以的是 \(n\) 而非 \(L\)：即使 \(a_{L + 1} \sim a_n\) 依赖于 \(a_1\sim a_L\)，但当 \(a_1\sim a_L\) 产生贡献时，它们也会相应产生贡献。
发现上式即 \(\dfrac{f_L\times cnt_x\times cnt_y}{L\times (L - 1) \times d ^ 2}\)，故只需求出 \(\sum\limits_{x\neq y} cnt_x \cdot cnt_y\)。这容易做到。
求 \(f, g\) 的时间复杂度在精细实现下均为线性。复杂度瓶颈在于为计算答案 \(\dfrac {\sum\limits_{i = 1} ^ n g_{\gcd(n, i)}}{\sum\limits_{i = 1} ^ n f_{\gcd(n, i)}}\)，求每个数与 \(n\) 的 \(\gcd\) 的线性对数，但常数非常小。注意特判 \(c = 1\) 的特殊情况。代码。
