「算法笔记」Polya 定理

V2AS问路

「算法笔记」Polya 定理

阅读原文时间：2022年07月06日阅读：2

一、前置概念

接下来的这些定义摘自置换群 - OI Wiki。

1. 群

若集合 \(s\neq \varnothing\) 和 \(S\) 上的运算 \(\cdot\) 构成的代数结构 \((S,\cdot)\) 满足一下性质：

封闭性：\(\forall a,b\in S,a\cdot b\in S\)。
结合律：\(\forall a,b,c\in S,(a\cdot b)\cdot c=a\cdot (b\cdot c)\)。
单位元：\(\exists e\in S,\forall a\in S,e\cdot a=a\cdot e=a\)。
逆元：\(\forall a\in S,\exists b\in S,a\cdot b=b\cdot a=e\)，称 \(b\) 为 \(a\) 的逆元，记为 \(a^{-1}\)。

则称 \((S,\cdot)\) 为一个群。例如，整数集合整数集的加法 \((\mathbb{Z},+)\) 构成一个群，单位元是 \(0\)，一个整数的逆元是它的相反数。

子群：若 \((S,\cdot)\) 是群，\(T\) 是 \(S\) 的非空子集，且 \((T,\cdot)\) 也是群，则称 \((T,\cdot)\) 是 \((S,\cdot)\) 的子群。

2. 置换

有限集合到自身的双射（即一一对应）称为置换。集合 \(S=\{a_1,a_2,\cdots,a_n\}\) 上的置换可以表示为

\(f=\begin{pmatrix} a_1,a_2,\cdots,a_n \\ a_{p_1},a_{p_2},\cdots,a_{p_n} \end{pmatrix}\)

意为将 \(a_i\) 映射为 \(a_{p_i}\)，其中 \(p_1,p_2,\cdots,p_n\) 是 \(1,2,\cdots,n\) 的一个排列。显然 \(S\) 上所有置换的数量为 \(n!\)。

3. 置换的乘法

对于两个置换 \(f=\begin{pmatrix} a_1,a_2,\cdots,a_n \\ a_{p_1},a_{p_2},\cdots,a_{p_n} \end{pmatrix}\) 和 \(g=\begin{pmatrix} a_{p_1},a_{p_2},\cdots,a_{p_n} \\ a_{q_1},a_{q_2},\cdots,a_{q_n} \end{pmatrix}\)，\(f\) 和 \(g\) 的乘积记为 \(f\circ g\)，其值为 \(f\circ g=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix}\)

简单来说就是先后经过 \(f\) 的映射，再经过 \(g\) 的映射。

4. 置换群

可以理解为是将置换作为元素的群。

易证，集合 \(S\) 上的所有置换关于「置换的乘法」满足封闭性（置换的乘积也是置换）、结合律、有单位元（恒等置换，即每个元素映射成它自己）、有逆元（交换置换表示中的上下两行），因此构成一个群。

这个群的任意一个子群即成为 置换群。

5. 循环置换

循环置换是一类特殊的置换。记

\(\begin{pmatrix} a_1,a_2,\cdots,a_m\end{pmatrix}=\begin{pmatrix} a_1,a_2,\cdots,a_{m-1},a_m\\a_2,a_3,\cdots,a_m,a_1\end{pmatrix}\)

为 \(m\) 阶循环。若两个循环置换不含有相同的元素，则称它们是 不相交 的。

有如下定理：任意一个置换都可以分解为若干不相交的循环置换的乘积，例如

\(\begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\a_3,a_1,a_2,a_5,a_4\end{pmatrix}=\begin{pmatrix}a_1,a_3,a_2\end{pmatrix}\circ \begin{pmatrix}a_4,a_5\end{pmatrix}\)

置换的 循环节数 是上述表示中循环置换的个数。如上述例子中循环节数为 \(3\)。

如果把元素视为图的节点，映射关系视为有向边，则每个节点的入度和出度都为 \(1\)，因此形成的图形必定是若干个环的集合，而一个环即可用一个循环置换表示。

二、Burnside 引理

Update on 2021.6.1

修改了表述，应该会清楚好懂一点。

\(n\) 个珠子的项链做黑白二染色，\(2^n\) 种。

但是项链可以旋转、对称，这些操作下相同的应该视为同一种。\(4\) 种：白白白，黑黑黑，白白黑，黑黑白。

Burnside 定理：

操作：旋转，对称，不变……（\(m\) 种操作）

等价类：可以通过互相转化的状态组成一个等价类。

想求：不同等价类总数。

对每一种操作 \(g\)，称在这种操作下不变的状态为 \(g\) 的不动点。

p>则不同等价类总数 \(=\frac{(\sum\limits_{g为m种操作之一}\quad\quad\quad g的不动点个数)}{m}\)。

Update 前

Update 前的表述，可跳过 QAQ。

对于 \(\forall k\in S\)，记 \(k\) 所在的 等价类 为 \(E_k\)，\(E_k=\{x\mid \exists f\in G,f(k)=x\}\)，即 \(k\) 在 \(G\) 的作用下所能变化成的所有元素的集合。（若 \(\exists f\in G,f(x)=y\)，则 \(x\) 和 \(y\) 等价，所有互相等价的元素组成一个等价类。其中 \(f(x)\) 表示 \(x\) 进行置换 \(y\) 的结果）

对于 \(\forall k\in S\)，记 \(k\) 的 不动置换类 为 \(Z_k\)，\(Z_k=\{f\mid f\in G,f(k)=k\}\)，即 \(G\) 中使 \(k\) 保持不变的置换的全体。

Burnside 引理：对于 \(\forall f\in G\)，记 \(D(f)=\sum\limits_{x\in S}[f(x)=x]\)，即 \(S\) 中在置换 \(f\) 下没有改变的元素的个数。设 \(L\) 为等价类个数。则：\(\displaystyle L=\frac{1}{|G|}\sum\limits_{f\in G} D(f)\)。证明。

换一种说法：对于一个置换 \(f\)，若一个着色方案 \(s\) 经过置换后不变，则称 \(s\) 为 \(f\) 的不动点。记 \(f\) 的不动点数目为 \(D(f)\)，则等价类个数为所有 \(D(f)\) 的平均值。

等价类个数可以理解为 本质不同 的方案数。

正常一点的语言：本质不同的方案数为在每个置换下稳定不动的方案的总和除以总置换数。

三、Pólya 定理

容易发现，在 Burnside 引理中，要计算 \(D(f)\) 的值不是很容易。Pólya 定理实质上是 Burnside 引理的一个扩展。

Pólya 定理：设 \(G\) 是 \(p\) 个对象的置换群，用 \(m\) 种颜色涂染 \(p\) 个对象。对于 \(\forall f\in G\)，记 \(c(f)\) 为置换 \(f\) 的循环节数，则不同染色方案为：\(\displaystyle L=\frac{1}{|G|}\sum\limits_{f\in G}m^{c(f)}\)。

要得到在置换下稳定不动的方案，即把置换的每个循环节都染上相同的颜色，所以 \(D(f)=m^{c(f)}\)。根据 Burnside 引理就能得到 Pólya 定理。

它解决的问题有限。通常用 DP 或组合数 来扩展此类问题。

黄队博客中的表述（Polya 计数法）：设 \(G\) 是 \(p\) 个对象的一个置换群，用 \(m\) 种颜色涂染 \(p\) 个对象，则不同染色方案为：

\(\displaystyle L=\frac{1}{|G|}(m^{c(g_1)}+m^{c(g_2)}+\cdot+m^{c(g_s)})\)

其中 \(G={g_1,\cdots,g_s}\)，\(c(g_i)\) 为置换 \(g_i\) 的环数。

四、应用与例题

对于没有接触过概念的读者来说，以上内容第一次读的时候可能会有些生涩，建议多读几遍。如果下面题目忘记写数据范围了那就去看原题吧 QwQ。

1. 常见置换的循环节数

1. 将长度为 \(n\) 的序列或环循环移 \(k\) 位：这个置换的循环节数为 \(\gcd(n,k)\)。具体地，这个置换是由 \(\gcd(n,k)\) 个 \(\frac{n}{\gcd(n,k)}\) 阶循环构成的。（\(\frac{\text{lcm}(n,k)}{k}=\frac{n}{\gcd(n,k)}\)）
2. 将长度为 \(n\) 的环沿对称轴反转。易知共有 \(n\) 种翻转置换。
- 若 \(n\) 为奇数，那么所有的轴会且只会经过一个环上的元素。每一个置换都是由一个 \(1\) 阶循环和 \(\frac{n-1}{2}\) 个 \(2\) 阶循环组成的，即 \(n\) 种翻转的循环节数均为 \(\frac{n+1}{2}\)。
- 否则，有两种情况：对称轴在两点之间时，对称轴左右两侧的点恰好一一配对，这 \(\frac{n}{2}\) 个轴不经过环上的元素，这些轴对应的翻转置换由 \(\frac{n}{2}\) 个 \(2\) 阶循环组成，即循环节数为 \(\frac{n}{2}\)；对称轴恰好穿过两点，这 \(\frac{n}{2}\) 个轴经过环上 \(2\) 个元素，这些轴对应的翻转置换由 \(2\) 个 \(1\) 阶循环和 \(\frac{n-2}{2}\) 个 \(2\) 阶循环组成，即循环节数为 \(\frac{n}{2}+1\)。

2. Luogu P1446 [HNOI2008]Cards

题目大意：有 \(n\) 张牌，染三种颜色，每种颜色规定数目。给出 \(m\) 种不同的洗牌方法。

两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。

求方案数对 \(p\) 取模的结果。

Solution：

把洗牌方法看作置换，染色方案看作“元素”。

输入数据保证任意多次洗牌都可用这 \(m\) 种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。所以它满足封闭性，并且存在逆元。我们需要加上 恒等置换（即每个元素映射成它自己），使其存在单位元。由于单位元满足 \(a\cdot e=a\)，所以并不会对答案产生影响。此时给出的置换是一个置换群，总置换数为 \(m+1\)。

因为染色存在数目限制，所以不能直接使用 Pólya 定理。

根据 Burnside 引理，本质不同的方案数为在每个置换下稳定不动的方案的总和（不动点数目之和）除以总置换数。

而要得到在置换下稳定不动的方案，那么就要把置换的每个循环节都 染上相同的颜色。

每个置换中都有若干个循环，根据给出的置换可以求出循环节数。考虑用 DP 求出每个循环节都染上相同的颜色，并且每种颜色的总和符合题目要求的方案总数。

所以，对于每一个置换，单独考虑每个循环染哪种颜色，可以通过一个类似背包的过程实现（把每一个循环看作一个物品，物品的重量为循环元素个数）。具体地，令 \(f_{i,j,k}\) 表示三种颜色分别用了多少的方案数。

答案为在每个置换下稳定不动的方案的总和除以总置换数。

#include
#define int long long
using namespace std;
const int N=30,M=70;
int n,R,B,G,m,mod,a[M],sz[M],cnt,f[N][N][N],ans;
bool vis[M];
int mul(int x,int n,int mod){ //保证 mod 为质数，可以使用快速幂求逆元
int ans=mod!=1;
for(x%=mod;n;n>>=1,x=x*x%mod)
if(n&1) ans=ans*x%mod;
return ans;
}
int solve(){
memset(vis,0,sizeof(vis)),cnt=0;
for(int i=1;i<=n;i++){ if(vis[i]) continue; int x=i,len=0; while(!vis[x]) len++,vis[x]=1,x=a[x]; //求循环中的元素个数 sz[++cnt]=len; //cnt: 循环节数 } memset(f,0,sizeof(f)),f[0][0][0]=1; for(int t=1;t<=cnt;t++) //类似背包的过程 for(int i=R;i>=0;i--)
for(int j=G;j>=0;j--)
for(int k=B;k>=0;k--){
if(i>=sz[t]) (f[i][j][k]+=f[i-sz[t]][j][k])%=mod;
if(j>=sz[t]) (f[i][j][k]+=f[i][j-sz[t]][k])%=mod;
if(k>=sz[t]) (f[i][j][k]+=f[i][j][k-sz[t]])%=mod;
}
return f[R][G][B];
}
signed main(){
scanf("%lld%lld%lld%lld%lld",&R,&G,&B,&m,&mod),n=R+G+B;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++) scanf("%lld",&a[j]);
ans=(ans+solve())%mod;
}
for(int i=1;i<=n;i++) a[i]=i; //加上恒等置换（自己到自己）
ans=(ans+solve())%mod,printf("%lld\n",ans*mul(m+1,mod-2,mod)%mod);
return 0;
}

3. Luogu P4980【模板】Pólya 定理

题目大意：给定一个 \(n\) 个点 \(n\) 条边的环，有 \(n\) 种颜色，给每个顶点染色，求本质不同的染色方案数，答案对 \(10^9+7\) 取模。

本质不同指的是不能通过旋转变得与其他染色方案相同。\(t\leq 10^3,n\leq 10^9\)。

Solution：

有 \(n\) 种循环移位，根据前面「常见置换的循环节数」中「将长度为 \(n\) 的环循环移 \(k\) 位：这个置换的循环节数为 \(\gcd(n,k)\)」以及 Pólya 定理可得：答案为 \(\displaystyle \frac{1}{n}\sum\limits_{k=1}^n n^{\gcd(n,k)}\)。

推一下式子：

枚举 \(\gcd\) 变为：\(\displaystyle \frac{1}{n}\sum\limits_{d\mid n} n^d \times \sum\limits_{k=1}^{\frac{n}{d}}[\gcd(k,\frac{n}{d})=1]\)。
后面那个式子是欧拉函数，直接代入：\(\displaystyle \frac{1}{n}\sum\limits_{d\mid n} n^d \varphi(\frac{n}{d})\)。

所以答案为 \(\displaystyle \frac{1}{n}\sum\limits_{d\mid n} n^d \varphi(\frac{n}{d})\)。

#include
#define int long long
using namespace std;
const int mod=1e9+7;
int t,n,ans;
int mul(int x,int n,int mod){
int ans=mod!=1;
for(x%=mod;n;n>>=1,x=x*x%mod)
if(n&1) ans=ans*x%mod;
return ans;
}
int phi(int n){ //求欧拉函数
int ans=n;
for(int i=2;i<=sqrt(n);i++){ if(n%i!=0) continue; ans=ans/i*(i-1); while(n%i==0) n/=i; } if(n>1) ans=ans/n*(n-1);
return ans%mod;
}
signed main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n),ans=0;
for(int i=1;i<=sqrt(n);i++){
if(n%i!=0) continue;
ans=(ans+mul(n,i,mod)*phi(n/i)%mod)%mod;
if(i*i!=n) ans=(ans+mul(n,n/i,mod)*phi(i)%mod)%mod; //套式子
}
printf("%lld\n",ans*mul(n,mod-2,mod)%mod);
}
return 0;
}

4. UVA10601 Cubes

题目大意：给正方体的 \(12\) 条棱染色，有 \(6\) 种颜色，每种颜色规定数目，求本质不同的方案数（旋转后相同的方案算同一种）。多组数据，\(1\leq t\leq 60\)。

Solution：

一个正方体共有 \(24\) 种旋转。根据这些不同的旋转方法，构造对应的关于边的置换群。

不旋转：\(1\) 种，分解为 \(12\) 个 \(1\) 阶循环。
以一对相对面的中心为轴：
- 旋转 \(90^{\circ}\)：\(6\) 种，分解为 \(3\) 个 \(4\) 阶循环。
- 旋转 \(180^{\circ}\)：\(3\) 种，分解为 \(6\) 个 \(2\) 阶循环。
以一对相对棱的中心为轴：
- 旋转 \(180^{\circ}\)：\(6\) 种，分解为 \(2\) 个 \(1\) 阶循环和 \(5\) 个 \(2\) 阶循环。
以一对对顶点为轴：
- 旋转 \(120^{\circ}\)：\(8\) 种，分解为 \(4\) 个 \(3\) 阶循环。