【算法笔记】Burnside引理与Pólya定理

前言

昨天hht来给窝萌增长了姿势水平
hht真的好神啊!伏地膜!

问:“你搞OI时如何平衡高考与竞赛”
hht:“我不用学习也能考很好,我在高一的时候已经把高中内容看完了”

正文

hht主要讲了Burnside引理的不完全证明和用Burnside引理推出Pólya定理
下面主要围绕这两方面来讨论

Burnside引理的不完全证明

有一个前置结论hht没有证明,说是需要引入很多无关的概念:

$|Z_k| \cdot |E_k| = |G|$

其中$|E_k|$表示一个等价类的大小,$|Z_k|$表示作用在这个等价类上使等价类不变的置换的数量
这个引理的证明似乎要用到群里边的轨道?我们可以参见这里:https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers
以下的内容建立在我们认为这个引理是正确的基础上

我们先来看一看Burnside引理的形式:$N = \frac{1}{|G|} \sum\limits_{g \in G}{\chi (g)}$
那么我们只需要证明:$N \cdot |G| = \sum\limits_{g \in G}{\chi (g)}$
对于$\sum\limits_{g \in G}{\chi (g)}$,我们实际上是先枚举置换,再枚举染色情况,再看是不是一个不动点
我们考虑换一个枚举顺序,我们枚举所有的染色情况,然后看有多少置换可以使这个染色情况成为不动点
那么这不就是$|Z_k| \cdot |E_k|$吗?于是$N \cdot |G| = \sum{|Z_k| \cdot |E_k|} = N \cdot G$,得证

使用Burnside引理推导Pólya定理

我们还是考虑枚举置换

如果一个置换可以使一种染色情况成为不动点
那么这个置换的每一个循环节只能被染成同一种颜色
所以每一种置换$g$我们有$k^{m(g)}$种染色方案($k$为可用的颜色数,$m(g)$为置换$g$的循环节)
于是我们就不用枚举所有的染色情况了,可以直接用$k^{m(g)}$计算

于是Pólya定理的公式就变成了$N = \frac{1}{|G|} \sum\limits_{g \in G}{k^{m(f)}}$
这个证明过程也非常直观地给出了Pólya定理不能解决带有颜色限制的染色问题的原因

【POJ 2409】Let it Bead

题目传送门:http://poj.org/problem?id=2409
中文题面:http://blog.csdn.net/ww140142/article/details/47003643

同1286

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

inline LL pow(int w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		t >>= 1, w *= w; 
	}
	return ret;
}

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

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	for (int col=read(),n=read();n && col;col=read(),n=read()) {
		LL vout = 0; int t = n;
		for (int i=1;i<=n;i++) vout += pow(col,GCD(i,n));
			
		if (n & 1) {for (int i=1;i<=n;i++) vout += pow(col,n/2+1); t += n;} 
		else {
			for (int i=1;i*2<=n;i++) vout += pow(col,n/2+1); t += n/2;
			for (int i=1;i*2<=n;i++) vout += pow(col,n/2); t += n/2;
		}
		
		vout /= t;
		printf("%lld\n",vout);
	} 
	return 0;
}

【POJ 1286】Necklace of Beads

题目传送门:http://poj.org/problem?id=1286

polya的板题,其中置换的循环节先用一下程序算,之后再写程序

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;

int to[MAXN],tag[MAXN],ty,delta,n;

inline int Get_M(){
	int ret = 0;
	for (int i=1,w;i<=n;i++) if (!tag[i]) {
		ret++; w = i;
		while (!tag[w]) tag[w] = 1, w = to[w];
	} return ret;
}

int main(){
	cin>>n>>delta>>ty;
	if (ty == 1) {
		for (int i=1;i<=n;i++) to[i] = i + delta;
		for (int i=1;i<=n;i++) if (to[i] > n) to[i] -= n;
	} else {
		for (int j=1,i=delta;j<=n;j++,i=++i>n?i-n:i) to[i] = n - i;
	} cout<<Get_M();
	return 0;
} 

主程序:

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int col = 3;

inline LL pow(int w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		t >>= 1, w *= w; 
	}
	return ret;
}

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

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	for (int n=read();~n;n=read()) {
		if (n == 0) {cout<<0<<endl; continue;}
		else { 
			LL vout = 0; int t = n;
			for (int i=1;i<=n;i++) vout += pow(col,GCD(i,n));
			
			if (n & 1) {for (int i=1;i<=n;i++) vout += pow(col,n/2+1); t += n;} 
			else {
				for (int i=1;i*2<=n;i++) vout += pow(col,n/2+1); t += n/2;
				for (int i=1;i*2<=n;i++) vout += pow(col,n/2); t += n/2;
			}
			
			vout /= t;
			printf("%lld\n",vout);
		}
	} 
	return 0;
}