【算法笔记】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定理不能解决带有颜色限制的染色问题的原因

【算法笔记】群论

首先是强烈推荐hht的bolg:http://techotaku.lofter.com/post/4856f0_59d4957
感觉看了之后群论就有了概念了啊!

至于细节方面,可以参考这篇blog:
http://blog.csdn.net/xuzengqiang/article/details/7476671

一些要点我还是写一写,免得以后忘了吧:
1)因为Polya只能解决不限使用次数的染色问题,所以Burnside也是有用的
2)Burnside用的是不动点的个数,Polya用的是置换的循环节
3)很多题目,给出的置换,不足以组成一个置换群,所以要先补足置换群

其实一些比较难的题都还没有做,比如:BZOJ_1488
所以,以后还要花时间再做一次专题才行啊!
另外,定理的证明还一点都不会,只能留到下一次专题一起做了吧!

【BZOJ 1004】[HNOI2008] Cards

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1004
数据传送门:http://pan.baidu.com/s/1jIc0r5s

这个题目,最开始无脑暴力,结果T到死 QAQ
总之就是Polya上不了,就只能上Burnside
然后直接求不动点也要T,于是只能搞三维背包
详见:hzwer.com/3222.html

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

const int MAXN = 21;
const int N = 61;
const int SGZ = 3;

int f[MAXN][MAXN][MAXN],p,col[MAXN],n,m,vout,tot,cnt[N],to[N],vis[N];

inline void Get_CIR(){
	tot = 0; memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++) scanf("%d",&to[i]);
	for (int i=1;i<=n;i++) if (!vis[i]) { cnt[++tot] = 0;
		for (int w=i;!vis[w];w=to[w]) cnt[tot]++, vis[w] = 1;
	} 
}

inline void DP(){
	memset(f,0,sizeof(f)); f[0][0][0] = 1;
	for (int t=1,w=cnt[1];t<=tot;w=cnt[++t]) for (int i=col[1];~i;i--) 
		for (int j=col[2];~j;j--) for (int k=col[3];~k;k--) if (f[i][j][k]){
			if (i + w <= col[1]) f[i+w][j][k] += f[i][j][k], f[i+w][j][k] %= p;
			if (j + w <= col[2]) f[i][j+w][k] += f[i][j][k], f[i][j+w][k] %= p;
			if (k + w <= col[3]) f[i][j][k+w] += f[i][j][k], f[i][j][k+w] %= p;
	}
	vout += f[col[1]][col[2]][col[3]]; vout %= p;
}

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

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

int main(){
	for (int i=1;i<=SGZ;i++) n += (col[i] = read()); m = read(), p = read();
	for (tot=1;tot<=n;tot++) cnt[tot] = 1; tot--; DP(); 
	for (int i=1;i<=m;i++) Get_CIR(), DP();
	printf("%d\n",vout*pow(m+1,p-2)%p);
	return 0;
}

【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;
}