hdu6314 容斥+数学

题意： n*m的矩阵可以涂黑白两色问至少A行B列为黑色的涂色方案种类数，答案对998244353取模，1<=n,m,A,B<=3000

题解： ans=sum{A,..n}sum(B,...m}*f[n-i][m-j] (i,j分别为前两个∑的迭代变量），f[a][b]表示a行b列中没有一行或者一列全部涂黑

由容斥定理 f[i][j]=sum{0,..i}sum{0,.j}*(-1)^(a+b)*2^(i-a)*(j-b) (a,b分别为前两个∑的迭代变量）。

代入得ans=sum{A,...n}sum{B,...m}sum{0,....n-i}sum{0,...m-j} n!m!(-1)^a+b2^{(n-i-a)(m-j-b)} /((n-i-a)!(m-j-b)!i!j!a!b!) (i,j,a,b)分别∑为的迭代变量

#include<cstdio>

using namespace std;

const int P=;

const int N=3e3+;

int e[N*N],fac[N],facn[N*N],pre[N][N],g[N][N];

inline int ksm(int x,int k){

    int ans=;

    for(;k;k>>=,x=1LL*x*x%P) if(k&) ans=1LL*ans*x%P;

    return ans;

}

void init(){

    int i,val;

    for(e[]=i=;i<=;++i) e[i]=2LL*e[i-]%P;

    for(fac[]=facn[]=i=;i<=;++i) fac[i]=1LL*i*fac[i-]%P,facn[i]=ksm(fac[i],P-);

    for(int i=;i<=;++i) for(int j=i;j>=;--j) {

        val=1LL*facn[j]*facn[i-j]%P;

        if((i-j)&) val=P-val;

        pre[i][j]=(val+pre[i][j+])%P;

    }

    for(int i=;i<=;++i) for(int j=;j<=;++j)

    g[i][j]=1LL*e[i*j]*facn[i]%P*facn[j]%P;

}

int main(){

    init();

    int n,m,A,B;

    while(~scanf("%d%d%d%d",&n,&m,&A,&B)){

        int ans=;

        for(int i=;i<=n-A;++i) for(int j=;j<=m-B;++j)

        ans=(ans+1LL*pre[n-i][A]*pre[m-j][B]%P*g[i][j]%P)%P;

        printf("%d\n",1LL*ans*fac[n]%P*fac[m]%P);

    }

}

巴特西

hdu6314 容斥+数学

最新文章

热门文章