【Luogu】 P6076 [JSOI2015]染色问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Luogu】 P6076 [JSOI2015]染色问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

点击打开链接

题目解法

可以一个一个条件考虑

只考虑条件 $1$
答案即为 $c+1)^{nm}$
考虑条件 $1, 2$
对每一行的方案数减去 $1$
答案即为 $c+1)^m-1)^n$
考虑条件 $1, 2, 3$
考虑容斥
容斥至少有 $i$ 列未被染色，即为 $g_i$
$g_i$ 即 $n$ 行 $m - i$ 列 $c$ 种颜色的方案数
$g_i=((c+1)^{m-i}-1)^n$
答案即为 $g_0*C^0_m-g_1*C^1_m+g_2*C^2_m-...$
考虑条件 $1, 2, 3, 4$
继续考虑容斥
先容斥至少有 $j$ 种颜色未被用到，记为 $f_j$
即 $n$ 行 $m$ 列 $c - j$ 种颜色的方案数
这就是第 $3$ 种情况的容斥
直接搬来即可
最终答案即为 $f_0*C^0_c-f_1*C^1_c+f_2*C^2_c-...$

两次容斥时间复杂度 $O (m c)$ ，求幂 $O (l o g n)$
总时间复杂度 $O(mc\;logn)$ 文章来源地址https://www.toymoban.com/news/detail-489599.html

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N(410),P(1e9+7);
int n,m,c,C[N][N]; 
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
int qmi(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=(LL)res*a%P;
		a=(LL)a*a%P;
	}
	return res;
}
int main(){
	n=read(),m=read(),c=read();
	C[0][0]=1;
	for(int i=1;i<N;i++)
		for(int j=0;j<=i;j++) C[i][j]=(!j||i==j)?1:(C[i-1][j]+C[i-1][j-1])%P;
	int ans=0;
	for(int i=0;i<=c;i++){//至少有i个颜色没出现 
		int res=0;
		for(int j=0;j<=m;j++){//至少有j列未染色 
			if(j&1) res=(res-(LL)qmi(qmi(c+1-i,m-j)-1,n)*C[m][j]%P+P)%P;
			else (res+=(LL)qmi(qmi(c+1-i,m-j)-1,n)*C[m][j]%P)%=P;
		}
		if(i&1) ans=(ans-(LL)res*C[c][i]%P+P)%P;
		else (ans+=(LL)res*C[c][i]%P)%=P;
	}
	printf("%d",ans);
	return 0;
}