BZOJ1004 [HNOI2008]Cards 【burnside定理 + 01背包】

题目链接

BZOJ1004

题解

burnside定理

在\(m\)个置换下本质不同的染色方案数，等于每种置换下不变的方案数的平均数

记\(L\)为本质不同的染色方案数，\(m\)为置换数，\(f(i)\)为置换\(i\)下不变的方案数，那么

\[L = \frac{1}{m}\sum\limits_{i = 1}^{m} f(i)
\]

在一个置换下一个方案不变，当且仅当该置换的任意一个循环节内部颜色相同

记循环节个数为\(c_i\)，色数为\(k\)且不限使用，那么该置换下不变的方案数为

\[k^{c_i}
\]

很好理解，每个循环节都能染\(k\)种颜色

于是乎我们就得到了\(polya\)引理：

在每种颜色数量不限情况下

\[L = \frac{1}{m}\sum\limits_{i = 1}^{m} k^{c_i}
\]

回到本题##

本题多了一个每种颜色数量的限制

我们只需计算出\(f(i)\)，即每种置换下不变的方案数

有\(c_i\)个循环节，每个循环节会消耗掉同一种颜色\(len_i\)个

将每个循环节看做一个有\(len_i\)体积的物品，就可以用一个三维\(01\)背包计算出方案数

题目中实际暗藏一个置换，就是什么置换也不用，实际上就相当于一个循环节数量为\(n\)的置换【置换群的单位元】

如果题中没给出这样的置换，需要我们手动加一个

这个置换的方案数可以直接确定，就是排列数\(\frac{n!}{Sr!Sb!Sg!}\)

这样我们就做完这题了

时间复杂度\(O(m*n*Sr*Sb*Sg)\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 65,maxm = 25,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int f[maxm][maxm][maxm],to[maxn],vis[maxn],v[maxn],fac[maxn];

int P,Sa,Sb,Sc,n,m,ans,flag;

void add(int& a,int b){

	a += b;

	if (a >= P) a -= P;

}

int qpow(int a,int b){

	int re = 1;

	for (; b; b >>= 1,a = 1ll * a * a % P)

		if (b & 1) re = 1ll * re * a % P;

	return re % P;

}

int main(){

	Sa = read(); Sb = read(); Sc = read(); m = read(); P = read();

	n = Sa + Sb + Sc; fac[0] = 1 % P;

	for (int i = 1; i < maxn; i++) fac[i] = 1ll * fac[i - 1] * i % P;

	for (int T = 1; T <= m ;T++){

		cls(vis); int tot = 0;

		for (int i = 1; i <= n; i++) to[i] = read();

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

			if (!vis[i]){

				int cnt = 1,u = i; vis[u] = true;

				while (!vis[to[u]]) u = to[u],vis[u] = true,cnt++;

				v[++tot] = cnt;

			}

		}

		if (tot == n) flag = true;

		cls(f); f[0][0][0] = 1;

		for (int i = 1; i <= tot; i++){

			for (int a = Sa; a >= 0; a--){

				for (int b = Sb; b >= 0; b--){

					for (int c = Sc; c >= 0; c--){

						if (a >= v[i]) add(f[a][b][c],f[a - v[i]][b][c]);

						if (b >= v[i]) add(f[a][b][c],f[a][b - v[i]][c]);

						if (c >= v[i]) add(f[a][b][c],f[a][b][c - v[i]]);

					}

				}

			}

		}

		add(ans,f[Sa][Sb][Sc]);

	}

	if (!flag){

		add(ans,1ll * fac[n] * qpow(fac[Sa],P - 2) % P * qpow(fac[Sb],P - 2) % P * qpow(fac[Sc],P - 2) % P);

		m++;

	}

	printf("%lld\n",1ll * ans * qpow(m,P - 2) % P);

	return 0;

}

巴特西

BZOJ1004 [HNOI2008]Cards 【burnside定理 + 01背包】

题目链接

题解

回到本题##

最新文章

热门文章