染色 [组合数容斥]

(mathcal{Description})

你要给一个(n imes m)的矩阵涂色，问有多少种染色方法使得每一行每一列都至少有一个格子被上了色
(n,mleq 10^6)对(998244353)取模
(mathcal{Solution})

直接求不好求，考虑容斥
两个限制条件，如果不想办法去掉一个影响，会十分烦

考虑强制令每一行都是合法的，在这样一个前提下容斥列不合法的情况
考虑不合法的情况，设最后只有(i)列有格子被染色了，考虑这样的方案数有多少
这肯定仍然是不好算的，因为我们要求的就是有(m)列被染色，所以把状态设为最多有(i)列被染色
这个状态看起来就既好求又好容斥了

再重复一遍状态:在每一行都合法的情况下,最多有(i)列被染色的方案数
现在我们可以认为只有(i)列要管,因为剩下(m-i)列都没有被染色
此时一行的染色方案数为(2^{i}),不能一个格子都没被染色,所以有(2^i-1)种染色方法
因为有(n)列，所以有(left(2^i-1 ight)^n)种染色方法满足在每一行都合法的情况下,最多有(i)列被染色的方案数

然后容斥,全部合法的染色方案=在每一行都合法的情况下最多(m)列被染色的方法-最多(m-1)列被染色的方法+最多(m-2)列被染色的方法...

根据奇偶决定正负

(mathcal{Code})

/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年10月25日 星期五 08时16分31秒
*******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 2000006;
const int mod = 998244353;
int n,m,ans;
int fac[maxn],ifac[maxn],inv[maxn],f[maxn];
void add (int &x,int y){	x=((x+y)%mod+mod)%mod;}
int C (int n,int m){	return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;}
//{{{init
void init ()
{
	fac[0]=ifac[0]=inv[1]=1;
	for (int i=2;i<=lim;++i)	inv[i]=(-1ll*mod/i*inv[mod%i]%mod+mod)%mod;
	for (int i=1;i<=lim;++i){
		fac[i]=1ll*fac[i-1]*i%mod;
		ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
	}
}
//}}}
//{{{ksm
int ksm (int a,int b)
{
	int s=1;
	for (;b;b>>=1,a=1ll*a*a%mod)
		if (b&1)	s=1ll*s*a%mod;
	return s;
}
//}}}
int main()
{
	init();
	scanf("%d%d",&n,&m);

	for (int i=1;i<=m;++i)	f[i]=1ll*C(m,i)*ksm(ksm(2,i)-1,n)%mod;
	for (int i=m;i>=1;--i)
		if ((m-i+1)&1)	add(ans,f[i]);
		else	add(ans,-f[i]);
	printf("%d
",ans);
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

染色 [组合数 容斥]

染色 [组合数容斥]