HNOI2008 Cards

wjh15101051's space

卧薪尝胆，厚积薄发。

HNOI2008 Cards

Date: Fri Dec 14 19:25:55 CST 2018

In Category: NoCategory

Description：

给 $n$ 点，每个点是 $1,2,3$ 三种颜色之一，限制了每种颜色的总个数，给出 $n$ 个置换，保证这 $n$ 个置换加上单位元可以构成一个群，问本质不同染色数量。

$1\leqslant \max(s1,s2,s3)\leqslant20,1\leqslant m\leqslant 60$

Solution：

显然的 $polya$ 定理，我们对于每一个置换，求出所有的循环，然后就变成了要求每个循环颜色相同，问方案数，那就做一个 $O(n^3)$ 的背包即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int s1,s2,s3,m,mod;

#define MAXN 70

int circ[MAXN];

int p[MAXN];

bool vis[MAXN];

int dfs(int k)

{

	vis[k] = true;

	int sum = 0;

	if(!vis[p[k]])sum = dfs(p[k]);

	return sum + 1;

}

int f[23][23][23];

int dp()

{

	memset(f,0,sizeof(f));

	f[0][0][0] = 1;

	for(int i = 1;i <= circ[0];++i)

	{

		for(int x = s1;x >= 0;--x)

		{

			for(int y = s2;y >= 0;--y)

			{

				for(int z = s3;z >= 0;--z)

				{

					if(x >= circ[i])f[x][y][z] = (f[x][y][z] + f[x - circ[i]][y][z]) % mod;

					if(y >= circ[i])f[x][y][z] = (f[x][y][z] + f[x][y - circ[i]][z]) % mod;

					if(z >= circ[i])f[x][y][z] = (f[x][y][z] + f[x][y][z - circ[i]]) % mod;

				}

			}

		}

	}

	return f[s1][s2][s3];

}

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % mod;

		a = a * a % mod;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%d%d%d%d%d",&s1,&s2,&s3,&m,&mod);

	int n = s1 + s2 + s3;

	int ans = 0;

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

	{

		for(int k = 1;k <= n;++k)scanf("%d",&p[k]);

		memset(vis,false,sizeof(vis));

		circ[0] = 0;

		for(int k = 1;k <= n;++k)if(!vis[k])

		{

			circ[++circ[0]] = dfs(k);

		}

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

	}

	circ[0] = 0;

	for(int i = 1;i <= n;++i)circ[++circ[0]] = 1;

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

	cout << ans * power(m + 1,mod - 2) % mod << endl;

	return 0;

}

In tag: 数学-polya定理

wjh15101051