CF1237F Balanced Domino Placements

比较有意思的 Counting，想到横竖两种骨牌的独立性就很好做了

考虑如果枚举最后放了 \(x\) 块横着的骨牌，\(y\) 块竖着的骨牌，直接考虑它们的摆放不方便，不妨转化一下

在所有空余的行中，选择 \(x+2y\) 行，且满足其中有 \(y\) 对相邻的行；在所有空余的列中，选择 \(2x+y\) 列，且满足其中有 \(x\) 对相邻的列

不难发现这样选出的行和列之间在组合时恰有 \(x!\times y!\) 种方案，且行列的选法是独立的，可以分开计算

考虑选取行的问题，先用 DP 算出选了恰好 \(y\) 对相邻的行的方案数，然后剩下的行用组合数算一下选单独的 \(x\) 行的方案数即可

DP 的状态也很简单，令 \(f_{i,j}\) 表示处理了前 \(i\) 行，此时选了 \(j\) 对相邻的行的方案数，转移显然

列的情况同理，预处理两个 DP 然后枚举 \(x,y\) 即可，总复杂度 \(O(nm)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=4005,mod=998244353;
int n,m,k,a,b,c,d,fact[N],ifac[N],f[N][N],g[N][N]; bool visr[N],visc[N];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<0||m<0||n<m) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	RI i,j; scanf("%d%d%d",&n,&m,&k);
	for (i=1;i<=k;++i)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		visr[a]=visr[c]=1;
		visc[b]=visc[d]=1;
	}
	int free_r=0,free_c=0; init(max(n,m));
	for (i=1;i<=n;++i) free_r+=!visr[i];
	for (i=1;i<=m;++i) free_c+=!visc[i];
	for (f[0][0]=1,i=0;i<n;++i)
	for (j=0;j<=n;++j) if (f[i][j])
	{
		inc(f[i+1][j],f[i][j]);
		if (i+2<=n&&!visr[i+1]&&!visr[i+2])
		inc(f[i+2][j+1],f[i][j]);
	}
	for (g[0][0]=1,i=0;i<m;++i)
	for (j=0;j<=m;++j) if (g[i][j])
	{
		inc(g[i+1][j],g[i][j]);
		if (i+2<=m&&!visc[i+1]&&!visc[i+2])
		inc(g[i+2][j+1],g[i][j]);
	}
	int ans=0;
	for (i=0;i<=n;++i) for (j=0;j<=m;++j)
	{
		if (i+2*j>free_r||2*i+j>free_c) continue;
		//printf("i = %d, j = %d, f[n][j] = %d, g[m][i] = %d\n",i,j,f[n][j],g[m][i]);
		inc(ans,1LL*f[n][j]*C(free_r-2*j,i)%mod*g[m][i]%mod*C(free_c-2*i,j)%mod*fact[i]%mod*fact[j]%mod);
	}
	return printf("%d",ans),0;
}