HDU - 6314 Matrix（广义容斥原理）

http://acm.hdu.edu.cn/showproblem.php?pid=6314

题意

对于n*m的方格，每个格子只能涂两种颜色，问至少有A列和B行都为黑色的方案数是多少。

分析

参考https://blog.csdn.net/IcePrincess_1968/article/details/81255138

重点在于计算容斥系数。

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = 3000 + 10;
const int maxm = 200000 + 10;
const int mod = 998244353;
int c[maxn][maxn],pw[maxn*maxn],fa[maxn],fb[maxn];
inline int add(int x){
if(x>=mod) x-=mod;
return x;
}
inline int sub(int x){
if(x<0) x+=mod;
return x;
}
inline void init() {
c[0][0]=1;
for(int i=1;i<maxn;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++) c[i][j]=add(c[i-1][j]+c[i-1][j-1]);
}
pw[0]=1;
for(int i=1;i<maxn*maxn;i++){
pw[i]=add(pw[i-1]+pw[i-1]);
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
//
freopen("output.txt", "w", stdout);
#endif
int n,m,A,B;
init();
while(~scanf("%d%d%d%d",&n,&m,&A,&B)){
fa[A]=1;
for(int i=A+1;i<=n;i++){
fa[i]=0;
for(int j=A;j<i;j++){
fa[i]=sub(fa[i]-1ll*c[i-1][j-1]*fa[j]%mod);
}
}
fb[B]=1;
for(int i=B+1;i<=m;i++){
fb[i]=0;
for(int j=B;j<i;j++){
fb[i]=sub(fb[i]-1ll*c[i-1][j-1]*fb[j]%mod);
}
}
int ans=0;
for(int i=A;i<=n;i++){
for(int j=B;j<=m;j++){
ans=add(ans+1ll*fa[i]*fb[j]%mod*c[n][i]%mod*c[m][j]%mod*pw[(n-i)*(m-j)]%mod);
}
}
printf("%dn",ans);
}
return 0;
}