Tag: Burnside

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

Qizy 16 Comments

前言

昨天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定理不能解决带有颜色限制的染色问题的原因

【BZOJ 1004】[HNOI2008] Cards

Qizy 85 Comments

题目传送门：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;
}