感觉，有时候把问题往网络流上想，不失为一种好的思路。
我们考虑 上填一个 的意义。则第 行和第 列需要填的和都会减少 。如果把他看作是一条 之间的边，问题就变为：在两个点集之间连边，可以有重边， 表示第 个点集的第 个点度数为 ，匹配的方案数。
此时发现值域只有 ，并且知道总数和其中一个就可以推出另外两个。联想到 AT_dp_j。从前往后匹配 ， 表示考虑第一个点集的前 个点，第二个点集中还剩 个 没匹配。转移是 naive 的，可以参考代码。
时空 ，注意边界条件。
code：
int n,m,dp[N][N],a[N],b[N];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
void Yorushika(){
scanf("%d",&n);
int x=0,y=0,z=0;
rep(i,1,n)scanf("%d",&a[i]),x+=a[i];
rep(i,1,n)scanf("%d",&b[i]),y+=b[i],z+=b[i]==1;
if(x!=y)return puts("0"),void(0);
dp[0][z]=1;int s=x;
rep(i,1,n){
if(!a[i]){
rep(j,0,n)dp[i][j]=dp[i-1][j];
continue;
}
rep(j,0,n){
if((s-j)&1)continue;
int k=(s-j)/2;
if(k<0)continue;
if(a[i]==2){
if(j>=2)dp[i][j-2]=Mod(dp[i][j-2],1ll*dp[i-1][j]*(1ll*j*(j-1)/2%mod)%mod);
if(k>=2)dp[i][j+2]=Mod(dp[i][j+2],1ll*dp[i-1][j]*(1ll*k*(k-1)/2%mod)%mod);
if(k>=1)dp[i][j]=Mod(dp[i][j],1ll*dp[i-1][j]*k%mod*(j+1)%mod);
}else{
if(j>=1)dp[i][j-1]=Mod(dp[i][j-1],1ll*dp[i-1][j]*j%mod);
if(k>=1)dp[i][j+1]=Mod(dp[i][j+1],1ll*dp[i-1][j]*k%mod);
}
}
s-=a[i];
}
printf("%d\n",dp[n][0]);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
作者以为只能是 01 矩阵，调了半个小时。什么时候才能不看错题啊。
