Pólya 定理学习笔记

在介绍\(Polya\) 定理前，先来介绍一下群论（大概了解一下就好）：

群是满足下列要求的集合：

封闭性：即有一个操作使对于这个集合中每个元素操作完都使这个集合中的元素
结合律：即对于上面那个操作有结合律
单位元：对于\(a * e = a\)则称\(e\)是集合\(A\)对于操作\(*\)（并不一定是相乘）的逆元
逆元：即有\(a * b = b * a = e\)对于元素\(a\)有逆元

置换群：

考虑这样的一个全置换集合，可以验证该集合为群。（置换不懂的话建议右转百度，这里不细说）

接下来介绍\(Burnside\)定理

对于一类染色问题，并统计在一些操作下的本质不同方案数有这样一个公式:

我们把所有的操作（类似于顺时针旋转，对称等等）写成一个置换群

则有答案为:

\(ans = \frac{1}{cnt}\sum_{f \in G}p(f)\)

其中\(p(f)\)指的是在该置换下不变的染色方案数。

举例有：

一个大小\(5\)的环，顺时针旋转了\(144\)度的置换为:

\(
\begin{pmatrix}
1&2&3&4&5\\
4&5&1&2&3
\end{pmatrix}
\)

以两种颜色染色则有:

\(
\begin{pmatrix}
1&1&1&1&1
\end{pmatrix}
\)

\(
\begin{pmatrix}
0&0&0&0&0
\end{pmatrix}
\)

两种方案满足对该置换不动。

接下来介绍\(Polya\)定理

考虑把置换写成循环的形式

\(
\begin{pmatrix}
1&2&3&4\\
1&2&3&4
\end{pmatrix}
\)

写作:\((1)(2)(3)(4)\)

\(
\begin{pmatrix}
1&2&3&4\\
3&4&1&2
\end{pmatrix}
\)

写作:\((1\ 3)(2\ 4)\)

则有\(Polya\)定理\(ans = \frac{1}{cnt}\sum_{f \in G}k^{m(f)}\)

\(k\)为染色数,\(m(f)\)为该置换拆解成的循环数。

【模板】Pólya 定理

考虑写出置换后，易证得顺时针旋转\(k\)次的置换的循环为\(gcd(n,k)\)

则有\(ans = \frac{1}{n}\sum_i^n n^{gcd(n,i)}\)

这样复杂度不在承受范围内，考虑枚举\(gcd(n,i)\)

\(ans = \frac{1}{n}\sum_{L|n} n^{L} * \varphi(\frac{n}{L})\)

这样就能在根号里做出答案了。

【模板】Pólya 定理

#include<iostream>

#include<cstdio>

#include<cmath>

#define ll long long

#define mod 1000000007

ll T,n;

inline ll pow(ll a,ll b){

	ll ans = 1;

	while(b){

		if(b & 1) ans = 1ll * ans * a % mod;

		a = a * a % mod;

		b >>= 1;

	}

	return ans % mod;

}

inline ll phi(int now){

	int ans = now;

	for(int i = 2;i * i <= now;++i){

		if(now % i)continue;

		ans = ans - ans / i;

		while(now % i == 0)

		now /= i;

	}

	if(now != 1)

	ans = ans - ans / now;

	return ans % mod;

}

inline ll get(int now){ll ans = phi(n / now) * pow(n,now) % mod;}

int main(){

	scanf("%lld",&T);

	while(T -- ){

		scanf("%lld",&n);

		ll ans = 0;

		for(int i = 1;i * i <= n;++i){

			if(n % i == 0){

				ans = (ans + get(i)) % mod;

				if(n / i != i)

				ans = (ans + get(n / i)) % mod;

			}

		}

		std::cout<<ans * pow(n,mod - 2) % mod<<std::endl;

	}

}

巴特西

Pólya 定理学习笔记

最新文章

热门文章