[容斥原理][HDU 6314][2018杭电多校训练2 G题] Matrix
题目大意
给定一个\(N\times M\)的矩阵,要将矩阵的每个格子涂成白色或黑色,问使得矩阵至少有\(A\)行\(B\)列被完全涂成黑色的方案数。
题解
设\(f[N][M]\)表示\(N\times M\)的矩阵任意行任意列都没有被完全涂成黑色的方案数。由容斥原理
\(f[N][M]=\sum_{r=0}^{N}\sum_{c=0}^{M} C_N^r\times C_M^c\times (-1)^{r+c}\times 2^{(N-r)*(M-c)}\)
\(Ans=\sum_{x=A}^{N}\sum_{y=B}^{M} C_N^x\times C_M^y\times f[N-x][M-y]\)
\(=\sum_{x=A}^{N}\sum_{y=B}^{M} C_N^x\times C_M^y\times(\sum_{r=0}^{N-x}\sum_{c=0}^{M-y} C_{N-x}^r\times C_{M-y}^c\times (-1)^{r+c}\times 2^{(N-x-r)(M-y-c)})\)
\(=\sum_{x=A}^{N}\sum_{y=B}^{M}\sum_{r=0}^{N-x}\sum_{c=0}^{M-y} C_N^x\times C_M^y\times C_{N-x}^r\times C_{M-y}^c\times (-1)^{r+c}\times 2^{(N-x-r)(M-y-c)}\)
\(C_N^x\times C_M^y\times C_{N-x}^r\times C_{M-y}^c=\frac{N!}{x!\times (N-x)!}\times \frac{M!}{y!\times (M-y)!}\times \frac{(N-x)!}{r!\times (N-x-r)!}\times\frac{(M-y)!}{c!\times (M-y-c)!}\)
\(=\frac{N!\times M!}{x!\times y!\times r!\times c!\times p!\times q!}\)
令\(p=N-x-r,q=M-y-c\),则
\(Ans=\sum_{x=A}^{N}\sum_{y=B}^{M}\sum_{r=0}^{N-x}\sum_{c=0}^{M-y} \frac{N!\times M!}{x!\times y!\times r!\times c!\times p!\times q!}\times (-1)^{r+c}\times 2^{pq}\)
\(=\sum_{x=A}^{N}\sum_{y=B}^{M}\sum_{r=0}^{N-x}\sum_{c=0}^{M-y} \frac{2^{pq}}{p!\times q!}\times \frac{N!\times(-1)^r}{x!\times r!}\times \frac{M!\times (-1)^c}{y!\times c!}\)
\(x+r=N-p, y+c=M-q,A\leq x, B\leq y\)
设\(Pre[s][A]\) 表示满足\(x+r=s,A\leq x\)的\(\frac{(-1)^r}{x!\times r!}\)的和,令\(g[p][q]=\frac{2^{pq}}{p!\times q!}\),则
\(Ans=N!\times M!\times \sum_{p=0}^{N-A}\sum_{q=0}^{M-B}Pre[N-p][A]\times Pre[M-q][B]\times g[p][q]\)
时间复杂度\(O(NM)\)。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define RG register int
#define LL long long
const LL MOD=998244353;
LL Inv[3010],InvFact[3010],Fact[3010],Pre[3010][3010];
int Pow2[9000010],g[3010][3010];
int N,M,A,B;
inline void Init(){
Inv[1]=1;InvFact[1]=1;Fact[1]=1;
InvFact[0]=Fact[0]=1;Pow2[0]=1;
for(RG i=2;i<=3000;++i){
Inv[i]=(MOD-MOD/i)*Inv[MOD%i]%MOD;
InvFact[i]=(InvFact[i-1]*Inv[i])%MOD;
Fact[i]=(Fact[i-1]*(LL)i)%MOD;
}
for(RG i=1;i<9000000;++i){
Pow2[i]=Pow2[i-1]<<1;
if(Pow2[i]>MOD) Pow2[i]-=MOD;
}
return;
}
inline void GetPre(){
for(RG x=3000;x>=0;--x){
for(RG r=0;r<=3000-x;++r){
LL temp;
if(r&1) temp=MOD-1;
else temp=1;
Pre[x+r][x]=(Pre[x+r][x]+((temp*InvFact[x])%MOD)*InvFact[r]%MOD)%MOD;
Pre[x+r][x-1]=(Pre[x+r][x-1]+Pre[x+r][x])%MOD;
}
for(RG y=0;y<=3000;++y)
g[x][y]=Pow2[x*y]*InvFact[x]%MOD*InvFact[y]%MOD;
}
return;
}
inline void Solve(){
LL Ans=0;
for(RG p=0;p<=N-A;++p)
for(RG q=0;q<=M-B;++q){
Ans=(Ans+(Pre[N-p][A]*Pre[M-q][B]%MOD)*g[p][q]%MOD);
if(Ans>MOD) Ans-=MOD;
}
Ans=(((Ans*Fact[N])%MOD)*Fact[M])%MOD;
printf("%lld\n",Ans);
return;
}
int main(){
Init();
GetPre();
while(~scanf("%d%d%d%d",&N,&M,&A,&B))
Solve();
return 0;
}