【容斥计数】Codeforces 998E Sky Full of Stars

题面在这里

题意：用3种颜色涂满\(n\times n\)的矩阵，求至少一行或一列颜色相同的方案数

​

先考虑至少一列同色，方案为\(3^{n^2}-(3^n-3)^n\)

再加上至少一行同色，这里有些方案是重复的，这些方案只可能是所有同色行的颜色相同（如果不同就不会有同色列了）

用容斥处理，枚举有\(i\)个同色行，则：

• 所有同色行颜色相同：那么每一列都不能是这种颜色的同色列，\(3 {n\choose i}(3^{n-i}-1)^n\)
• 其他：不会有同色列产生，答案是\({n \choose i}(3^i-3)3^{n(n-i)}\)

​

示例程序：

#include<cstdio>
typedef long long ll;

const int maxn=1000005,MOD=998244353;
int n; ll fac[maxn],inv[maxn];
inline ll ksm(ll a,ll b){
	ll res=1,w=a;
	while (b){
		if (b&1) (res*=w)%=MOD;
		(w*=w)%=MOD;
		b>>=1;
	}
	return res;
}
inline ll C(ll x,ll y){
	return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
int main(){
	scanf("%d",&n);
	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(fac[i-1]*i)%MOD;
	inv[n]=ksm(fac[n],MOD-2);for (int i=n;i;i--) inv[i-1]=(inv[i]*i)%MOD;
	ll ans=(ksm(3,(ll)n*n)-ksm(ksm(3,n)-3,n))%MOD;
	for (int i=1;i<=n;i++){
		ll del=3*C(n,i)%MOD*ksm(ksm(3,n-i)-1,n)%MOD+C(n,i)*(ksm(3,i)-3)%MOD*ksm(3,(ll)n*(n-i))%MOD;del%=MOD;
		if (i&1) (ans+=del)%=MOD;else (ans-=del)%=MOD;
	}
	printf("%lld",(ans+MOD)%MOD);
	return 0;
}