【BZOJ4487】[JSOI2015]染色问题（容斥）

题面

题解

看起来是一个比较显然的题目？

首先枚举一下至少有多少种颜色没有被用到过，然后考虑用至多\(k\)种颜色染色的方案数。

那么显然没有颜色的限制，只有行列的限制。

那么我们钦定行必须被染色，这样子每一行的染色方案之和列数和颜色数相关，那么再容斥一下有多少列没有被染色就行了。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 444

#define MOD 1000000007

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}

int n,m,c,ans,C[MAX][MAX];

int Calc(int c)

{

	int ret=0;

	for(int i=0,d=1;i<=m;++i,d=MOD-d)

	{

		int v=fpow(c,m-i)-1;

		ret=(ret+1ll*d*fpow(v,n)%MOD*C[m][i])%MOD;

	}

	return ret;

}

int main()

{

	n=read();m=read();c=read()+1;

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

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

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

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;

	for(int i=0,d=1;i<c;++i,d=MOD-d)ans=(ans+1ll*d*Calc(c-i)%MOD*C[c-1][i]%MOD)%MOD;

	printf("%d\n",ans);

	return 0;

}

巴特西

【BZOJ4487】[JSOI2015]染色问题（容斥）

【BZOJ4487】[JSOI2015]染色问题（容斥）

题面

题解

最新文章

热门文章