【BZOJ 1004】【HNOI 2008】Cards

http://www.lydsy.com/JudgeOnline/problem.php?id=1004

注意数据给出的m是一个没有单位元的置换群！

用Burnside引理，然后对每个置换群dp一下就可以了。

#include<cstdio>

#include<bitset>

#include<cstring>

#include<algorithm>

using namespace std;

int a[63], Sr, Sb, Sg, m, p, n, ans = 0;

int ipow(int w, int b) {

	int ret = 1;

	while (b) {

		if (b & 1) ret = ret * w % p;

		w = w * w % p;

		b >>= 1;

	}

	return ret;

}

int f[63][63][63][63], w[63], tot;

bitset <64> vis;

int dp() {

	vis.reset(); tot = 0;

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

		if (!vis[i]) {

			vis[i] = 1;

			w[++tot] = 1;

			int tmp = a[i];

			while (!vis[tmp]) {

				vis[tmp] = 1;

				++w[tot];

				tmp = a[tmp];

			}

		}

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

		for (int R = 0; R <= Sr; ++R)

			for (int B = 0; B <= Sb; ++B)

				for (int G = 0; G <= Sg; ++G) {

					f[i][R][B][G] = 0;

					if (R >= w[i]) (f[i][R][B][G] += f[i - 1][R - w[i]][B][G]) %= p;

					if (B >= w[i]) (f[i][R][B][G] += f[i - 1][R][B - w[i]][G]) %= p;

					if (G >= w[i]) (f[i][R][B][G] += f[i - 1][R][B][G - w[i]]) %= p;

				}

	return f[tot][Sr][Sb][Sg];

}

int main() {

	scanf("%d%d%d%d%d", &Sr, &Sb, &Sg, &m, &p);

	n = Sr + Sb + Sg; f[0][0][0][0] = 1;

	for (int j = 1; j <= n; ++j) a[j] = j;

	(ans += dp()) %= p;

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

		for (int j = 1; j <= n; ++j) scanf("%d", a + j);

		(ans += dp()) %= p;

	}

	printf("%d\n", ans * ipow(m + 1, p - 2) % p);

	return 0;

}

巴特西

【BZOJ 1004】【HNOI 2008】Cards

最新文章

热门文章