【题解】[Codeforces 1503E] 2-Coloring | 20210929 模拟赛 法阵（magic）【组合数 前缀和】

题目链接

题目链接

题意

为 (n imes m) 的网格黑白染色，使得每行恰有一个黑色连续段，每列恰有一个白色连续段，求方案数。(n,mleq 2021)

题解

以上前两种情况借助组合数+前缀和+组合数+前缀和+组合数+前缀和+组合数+前缀和处理，会算重最后一种情况。

#include<bits/stdc++.h>
using namespace std;
const int N=4050,mod=998244353;
int getint(){ int x;scanf("%d",&x);return x; }
int c[N][N];

int _(int x){ return x>=mod?x-mod:x; }

int s0[N],s1[N],s2[N],s3[N];
int t1[N][N],t2[N][N];

int main(){
//	freopen("magic.in","r",stdin);
//	freopen("magic.out","w",stdout);
	int n=getint(),m=getint();
	if(n==1||m==1)return puts("0"),0;
	int k=n+m;
	for(int i=c[0][0]=1;i<=k;i++){
		for(int j=c[i][0]=1;j<=i;j++)
			c[i][j]=_(c[i-1][j]+c[i-1][j-1]);
	}
	int ans=0;
	for(int x=1;x<m;x++){
		s0[0]=1;
		for(int i=1;i<=n;i++)
			s0[i]=(s0[i-1]+c[x-1+i][i])%mod;
		for(int i=1;i<=n;i++)
			s1[i]=(s1[i-1]+s0[i-1]*1ll*c[n-i+x-1][n-i])%mod;
		for(int i=1;i<=n;i++)
			s2[i]=(s2[i-1]+s1[i]*1ll*c[m-x-1+i][i])%mod;
		for(int i=1;i<=n;i++)
			s3[i]=(s3[i-1]+s2[i-1]*1ll*c[m-x-1+n-i][n-i])%mod;
		ans=(ans+s3[n])%mod;
	}
	swap(n,m);
	memset(s0,0,sizeof(s0));
	memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
	memset(s3,0,sizeof(s3));
	for(int x=1;x<m;x++){
		s0[0]=1;
		for(int i=1;i<=n;i++)
			s0[i]=(s0[i-1]+c[x-1+i][i])%mod;
		for(int i=1;i<=n;i++)
			s1[i]=(s1[i-1]+s0[i-1]*1ll*c[n-i+x-1][n-i])%mod;
		for(int i=1;i<=n;i++)
			s2[i]=(s2[i-1]+s1[i]*1ll*c[m-x-1+i][i])%mod;
		for(int i=1;i<=n;i++)
			s3[i]=(s3[i-1]+s2[i-1]*1ll*c[m-x-1+n-i][n-i])%mod;
		ans=(ans+s3[n])%mod;
	}
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
			ans=(ans-c[i-1+j][j]*1ll*c[n-i+j-1][n-i]%mod*c[n-i-1+m-j][m-j]%mod*c[i+m-j-1][i])%mod;
	
	ans=(ans%mod+mod)%mod;
	ans=ans*2ll%mod;
	cout<<ans<<endl;
}