测试

· · 个人记录

Burnside 引理 & Pólya 定理

Burnside 引理 & Pólya 定理能够用来解求本质不同的方案数这类问题。

考虑到定理的证明依赖于群论，而萌新可能对群论比较陌生，因此从群论相关知识讲起。

群论知识参考了许多资料（见本文引用资料），把本人认为简洁易于理解的讲解保留了下来，而对于一些理论。证明使用了自己的讲述方法/证法，如果发现不严谨或者笔误指出请指出 orz。

写这份博客的时候电脑曾经停电丢失了数据，写到一半的进度没了，我厄厄。

群论相关知识

半群

群

对于每个元素均有逆元的含幺半群 G 称为群。

若运算又满足交换律，称 G 为交换群或阿贝尔（Abel）群。

群 G 的元素数 |G| 称为群的阶。

个人认为，把群看成是具有一定约束并且支持运算 \cdot 的集合会比较容易理解相关内容。

群的性质总结

由上文所述，群满足性质：

当然，如果 G 在 \cdot 下满足上述四个性质，那么称 (G, \cdot) 为一个群。

例子

上面给了半群与群的定义，现举个例子：

对于自然数集 N，(N, +) 为含幺交换半群，幺元为 0，不是的群的原因是 N 中非 0 的数均不存在逆元。

而整数集 Z 对于加法是交换群，因为对于 x\in Z，-x 为对应的逆元，事实上，它被称为整数加法群。

子群

若 H \subseteq G 且在 (H, \cdot) 为群，称 H 为 G 的子群，记为 H \leq G。

验证子集 H 为 G 的子群只需验证以下三点：

陪集

陪集是由任意固定的 g\in G 与 G 子群 H 生成的集合，

其中左陪集为：gH = \{gh | h\in H\}

右陪集为：Hg = \{hg | h\in H\}

陪集的性质：

陪集定理

对于 H 两个左（右）陪集，要么相等，要么交集为 \varnothing。

证明：

如果陪集 gH, g'H 存在交集，假设交集的一个元素为 gh = g'h'（h, h'\in H），

显然有 gh H = g'h' H，因为 hH = h'H = H，因此 gH = g'H

利用陪集定理，我们有分拆：G = \cup g_iH，叫做 G 对子群 H 的左陪集分解。

其中左陪集的个数记为 [G:H]，称为子群 H 对于 G 的指数。

进而，我们显然有：设 G 为有限群，H\leq G，则 |G| = |H|[G:H]。（拉格朗日（J.Lagrange） 定理）

置换

集合 \Sigma 到自身每个一一对应 \sigma 叫做 \Sigma 上的一个置换。若 \Sigma 为有限集，此置换可表示为：

\sigma = \begin{pmatrix} a_1 & a_2 & \dots & a_n \\ \sigma(a_1) & \sigma(a_2) & \dots & \sigma(a_n) \\ \end{pmatrix} $$ \sigma ^ {-1} = \begin{pmatrix} \sigma(a_1) & \sigma(a_2) & \dots & \sigma(a_n) \\ a_1 & a_2 & \dots & a_n \\ \end{pmatrix} $$ 两个置换 $\sigma, \tau$ 的乘积定义为 $\Sigma \to \Sigma$ 映射的合成：$(\sigma \tau) (a_i) = \sigma(\tau(a_i))$，其中 $i \in [1, n]$。 例如， $$ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 \\ \end{pmatrix} $$ 轮换（循环置换）是一类特殊的置换，表示为 $$ \begin{pmatrix} a_1 & a_2 & \dots & a_{n-1} & a_n \\ a_2 & a_3 & \dots & a_n & a_1 \\ \end{pmatrix} $$ 每个置换均可写成一些**轮换**的乘积（轮换的次序可随意写），使不同轮换中没有公共元素，长为 $1$ 的置换往往**略去不写**，如： $$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 2 & 5 & 4 & 6 \\ \end{pmatrix} = (1, 3, 2)(4, 5) = (4, 5)(1, 3, 2) $$ #### 置换群 上面已说明置换的乘积仍为**置换**，且存在逆元。而对于置换的幺元显然是**恒等置换**（简单来说就是 $a_i \to a_i$）。 因此我们可以定义一个 $S(\Sigma)$ 表示 $\Sigma$ 上全体置换构成的**集合**，这是一个 $n!$ 元群，叫做集合 $\Sigma$ 上的对称群。 而它的每个子群都叫集合 $\Sigma$ 上的**置换群**。 ### Burnside 引理 & Pólya 定理 给定集合 $X$ 和**置换群** $G$。 > 如果感觉到十分抽象的话，不妨代入下面的情境（意义）对下文的内容进行理解： > > $A$ 表示待染色物品**集合**。 > > $B$ 表示支持染的颜色的**集合**。 > > $X$ 表示染色方案**集合**。 > > $G$ 表示支持的变换。 > > $X/G$ 表示**本质不同**的染色方案**集合**。 > > $X^g$ 表示经过一个变换 $g$ 后保持不变的**染色方案**对应的**集合**。 > > 比如说：给你一串共 $n$ 个珠子，支持旋转变换 $G$（可以看作是置换的一种）（这意味着如果两种染色方案在旋转后一样视为**本质相同**），每个珠子可以被染成 $m$ 种颜色（也就是说方案集 $X$ 的大小为 $m ^ n$），求本质不同的染色方案数（也就是 $|X/G|$） #### 轨道-稳定子定理 ##### 轨道 $\forall x\in X$, 称 $G(x) = \{g(x) | g\in G\}$ 为 $x$ 的**轨道**。 ##### 稳定子 $\forall x\in X$，称 $G ^ x = \{g | g(x) = x, g\in G \}$ 为 $x$ 的**稳定子**。 $$ |G| = |G ^ x||G(x)| $$ 先证明 $G^x$ 是 $G$ 的**子群**： - 封闭性：对于 $G^x$ 的元素 $g, g'$，有 $(gg')(x) = x$，故 $gg'\in G^x

由拉格朗日定理，|G| = |G ^ x| [G: G^x]

故下面只需证 [G: G^x] = |G(x)|，也就是左陪集的个数等于 x 轨道的个数。

证明：

考虑证明存在 G(x) 到 G^x 左陪集的一一映射：

注意到对于每个 gG^x，有 gG^x(x) 的元素均相同，这意味着每个左陪集 gG^x 能够对应一个 G(x) 的元素 g(x)；而对于不同的左陪集 gG^x, g'G^x，因为 g\ne g'，因此必然满足相应的 g'(x) \ne g(x)。

因此有 G(x) 到 G^x 左陪集的一一映射关系。

Burnside 引理

\begin{aligned} \sum_{g\in G}|X^g| &= |\{(g,x) | (g,x)\in G\times X, g(x) = x\}| \\ &= \sum_{x\in X}|G^x| \\ &= \sum_{x\in X}\frac{|G|}{|G(x)|} \end{aligned}

下面结合实际意义进行推导：

对于本质相同的一组（染色方案）x，它们的轨道数都是 G(x)，因此有：

\begin{aligned} \sum_{x\in X}\frac{1}{|G(x)|} &= |X/G| \end{aligned}

故我们有 Burnside 引理：

|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|

这意味着，对于实际的计数问题，在给出变换的种类数 |G| 后，我们只需要求出染色方案在各种变换下保持不动的数量的和（即 \sum_{g\in G}|X^g|），那么我们就可以求出本质不同的染色方案数了。

Pólya 定理

考虑到 Burnside 引理需要求的 \sum_{g\in G}|X^g| 在实际统计中时间复杂度较高，而很多问题都是求解 A\to B 所有可能的映射（也就是比较特殊的 X）所对应的染色方案（共 |B| ^ {|A|} 种）中本质不同的数量。

那么，在这样的问题中，可以使用 Pólya 定理：

|X/G| = \frac{1}{|G|}\sum_{g\in G}|B|^{c(g)}

证明：

注意到对于置换 g，对于其拆分出的每个循环置换中的颜色必须相同，根据乘法原理，可知共有 |B | ^ {c(g)} 种

这意味着满足在 g 作用下保持不变的方案 x 数量 |X^g| 等于 |B| ^ {c(g)}。

也就是 |B| ^ {c(g)} = |X ^ g|，证毕。

例题

https://www.luogu.com.cn/problem/P4980

解答

考虑使用 Pólya 定理：

只需统计对于每个置换 g 的 c(g) 值即可。

而对于本题，置换的形式就是 k \in [0, n-1] 的循环移位，例如 n=4, k=2：

g = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ \end{pmatrix}

那么上例的 c(g) 值就是 2。

现在的问题就是：给定 n, k，求相应的 c(g) 值。

其实就是求给定大小为 n 的环，能拆分成多少个步长为 k 的环，比如上面的例子就是能拆成两个环：(1, 3), (2, 4)。

所以考虑求每个环的大小 size（容易发现每个环大小相等），那么 c(g) = \frac{n}{size}。

而 size 是满足 n | tk 的最小的 t，所以 size = \frac{n}{\gcd(n, k)}。

现在，由上述推理以及 Pólya 定理，题目所求的答案 Ans 就是：

Ans = \frac{1}{|n|}\sum_{k=0}^{n-1} |n|^{\gcd(n, k)}

当然因为直接枚举的复杂度为 O(TN)，会超时。

考虑根据 \gcd 的值对上述和式进行分块，可以从枚举 n 的因子 d 入手：

Ans = \frac{1}{|n|}\sum_{d|n} |n|^{d} \varphi(\frac{n}{d})

复杂度为 O(T \cdot \sqrt N \cdot \rm{log}N)，可以通过。

代码实现

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mod=1e9+7;

int fpow(int x, int p){
    int res=1;
    for(; p; p>>=1, x=x*x%mod) if(p&1) res=res*x%mod;
    return res;
}

int gcd(int a, int b){
    return b? gcd(b, a%b): a;
}

int inv(int x){
    return fpow(x, mod-2);
}

int phi(int x){
    int res=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1) res=res/x*(x-1);

    return res;
}

signed main(){
    int T; cin>>T;
    while(T--){
        int n; cin>>n;
        int res=0;
        for(int i=1; i<=n/i; i++){
            if(n%i==0){
                res=(res+fpow(n, i)*phi(n/i)%mod)%mod;
                if(n/i!=i) res=(res+fpow(n, n/i)*phi(i)%mod)%mod;
            }
        }
        cout<<res*inv(n)%mod<<endl;
    }   
    return 0;
}

引用资料

https://cp-algorithms.com/combinatorics/burnside.html

https://zhuanlan.zhihu.com/p/294221308

https://oiwiki.com/math/permutation-group/

冯克勤,李尚志,章璞.[M].合肥:中国科学技术大学出版社,2018