赛时没写出精细实现.. 比较坏

原题:P14396 [JOISC 2016] 棋盘游戏 / Solitaire

首先我们来考虑哪些情况有解。我们发现角上的四个点只能是初始存在，上下两条边上的点只能通过条件(2)填入。因此判定条件可知。（虽然但是在SYOJ的数据中并没有无解的情况）

同时，我们可以得到，上下边上的点均可以在第一步被填出，因此主要考虑中间的点。我们所做的相当于给中间的点找一个顺序。

如果点是由(1)填入的，那么它们互不影响。否则，需要比较相邻点被填入时刻的大小关系。

因此我们有$dp$状态：$dp[i][j][op]$表示已经处理了前$i$列，$(2,j)$在前$i$列的所有空格中第$j$个被填入，钦定通过方式$(op+1)$填入。其中$op\in \{ 0,1 \}$。

若$(1,i)$，$(3,i)$均出现在$(2,i)$之前，则认为它只通过$(1)$填入。这样即可不重不漏。

在$dp$的过程中，若$a_{2,i}=1$，则将前面的所有转移至$dp_{i,0,0}$，以此减少讨论。

转移的过程可以看做是钦定这一列的空行被填入的时刻，并将前$i-1$列的部分插入。这样会比较好想。

具体的$dp$式子写起来比较令人疲惫，读者自己推去吧。

还有一个点，在转移的时候只能处理 $1$到前$i$列$0$的个数，否则会记入不存在的情况。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int jc[6010],nyjc[6010];
int qpow(int x,int y){
	int sum=1;
	while(y){
		if(y&1) sum=sum*x%mod;
		x=x*x%mod;
		y>>=1;
	}return sum;
}
int C(int x,int y){
	if(x<y) return 0;
	return jc[x]*nyjc[y]%mod*nyjc[x-y]%mod;
}
int n;
int a[4][2020],sum0[2020];
int dp[6010][2],sum[6010][2];
signed main() {
	jc[0]=nyjc[0]=1;
	for(int i=1;i<=6000;i++){
		jc[i]=jc[i-1]*i%mod;
		nyjc[i]=qpow(jc[i],mod-2);
	}
	cin>>n;
	for(int t=1;t<=3;t++) {
		for(int i=1;i<=n;i++) {
			char c;cin>>c;
			a[t][i]=(c=='1'?1:0);
			if(a[t][i]==0) sum0[i]++;
		}
	}
	for(int i=1;i<n;i++){
		if(a[1][i]==a[1][i+1]&&a[1][i]==0){
			cout<<0;return 0;
		}if(a[3][i]==a[3][i+1]&&a[3][i]==0){
			cout<<0;return 0;
		}
	}if(a[1][1]==0||a[1][n]==0||a[3][1]==0||a[3][n]==0){
		cout<<0;return 0;
	}
	for(int i=1;i<=n;i++) sum0[i]+=sum0[i-1];
	int V=3*n;
	for(int i=0;i<=V;i++) sum[i][0]=1;
	for(int i=1;i<=n;i++){
		int tms=sum0[i]-sum0[i-1],sl=sum0[i-1];
		if(a[2][i]==1){
			dp[0][0]=(sum[V][0]+sum[V][1])*C(sl+tms,tms)*jc[tms]%mod;
		}else{
			for(int j=1;j<=sum0[i];j++){
				dp[j][0]=sum[V][0]*C(j-1,tms-1)%mod*jc[tms-1]%mod;
				dp[j][0]=(dp[j][0]+(sum[V][1]-sum[max(0ll,j-tms)][1])*C(j-1,tms-1)%mod+mod)%mod;
				if(tms==2) dp[j][1]=sum[j-1][0]*C(sl+tms-j,tms-1)%mod;
				else if(tms==3){
					dp[j][1]=sum[j-1][0]*C(sl+tms-j,tms-1)%mod*jc[tms-1]%mod;
					if(j>=2) dp[j][1]=(dp[j][1]+sum[j-2][0]*C(j-1,1)%mod*C(sl+tms-j,1)%mod*2%mod)%mod;
				} 
				else dp[j][1]=0;
			}
		}
		sum[0][0]=dp[0][0];sum[0][1]=dp[0][1];
		dp[0][0]=dp[0][1]=0;
		for(int j=1;j<=V;j++){
			sum[j][0]=sum[j-1][0]+dp[j][0];
			sum[j][1]=sum[j-1][1]+dp[j][1];
			sum[j][0]%=mod;sum[j][1]%=mod;
			dp[j][0]=dp[j][1]=0;
		}
	}
	cout<<sum[V][0];
	return 0;
}