题目链接
题解
首先一个很自然的思路是，设(dp[i][j])表示选了前(i)列，第(2)行第(i)列的格子是第(j)个被填上的。
还要加个第三维(0/1)，表示第(2)行第(i)列不是/是这一列最后一个被填上的（这决定了它是被上下填上还是被左右填上）。
转移: 若第(2)行第(i)列是棋子，则所有的都转移到(f[i][0][0]).
(1) (0
ightarrow 0), 两个互不影响，可以从任意的(j')的(f[i][j'][0])转移过来，组合数选出顺序。
(2) (1
ightarrow 0), ((2,i))要在((2,i-1))之前选，可以从大于当前的(j')转移过来，同样用组合数选出顺序。
(3) (0
ightarrow 1), ((2,i))要在((2,i-1))之后选。但是这里要求((2,i))早于((1,i))和((3,i))中的至少一个，因此需要分类讨论。我的代码里第一个转移是((2,i))比上下两个（如果存在）都晚，第二个转移是((2,i))早于上下两个中的一个。
代码
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
using namespace std;
const int N = 2000;
const int P = 1e9+7;
char a[3][N+3];
llong dp[N+3][N*3+3][2];
llong fact[N*3+3],finv[N*3+3];
int n;
llong quickpow(llong x,llong y)
{
llong cur = x,ret = 1ll;
for(int i=0; y; i++)
{
if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}
cur = cur*cur%P;
}
return ret;
}
void updsum(llong &x,llong y) {x = (x+y)%P;}
int main()
{
fact[0] = 1ll; for(int i=1; i<=N*3; i++) fact[i] = fact[i-1]*i%P;
finv[N*3] = quickpow(fact[N*3],P-2); for(int i=N*3-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;
scanf("%d",&n);
for(int i=0; i<=2; i++) scanf("%s",a[i]+1);
if(a[0][1]=='x'||a[0][n]=='x'||a[2][1]=='x'||a[2][n]=='x') {puts("0"); return 0;}
for(int i=2; i<=n; i++) {if((a[0][i]=='x'&&a[0][i-1]=='x')||(a[2][i]=='x'&&a[2][i-1]=='x')) {puts("0"); return 0;}}
int sum = a[1][1]=='x'?1:0;
dp[1][sum][0] = 1ll;
for(int i=2; i<=n; i++)
{
for(int j=1; j<=sum; j++) {updsum(dp[i-1][j][0],dp[i-1][j-1][0]),updsum(dp[i-1][j][1],dp[i-1][j-1][1]);}
int now = (a[0][i]=='x')+(a[2][i]=='x'); sum += now+(a[1][i]=='x');
if(a[1][i]=='o')
{
dp[i][0][0] = (dp[i-1][sum-now][0]+dp[i-1][sum-now][1])*fact[sum]%P*finv[sum-now]%P;
continue;
}
for(int j=1; j<=sum; j++)
{
if(j-now-1>=0)
{
updsum(dp[i][j][0],(dp[i-1][sum-now-1][1]-dp[i-1][j-now-1][1]+dp[i-1][sum-now-1][0]+P)*fact[j-1]%P*finv[j-now-1]%P);
}
if(now>=1)
{
updsum(dp[i][j][1],dp[i-1][min(j-1,sum-now-1)][0]*fact[sum-j]%P*finv[sum-j-now]);
if(now==2&&j>=2) {updsum(dp[i][j][1],dp[i-1][j-2][0]*(sum-j)%P*(j-1)*2ll%P);}
}
// printf("dp[%d][%d]=(%lld,%lld)
",i,j,dp[i][j][0],dp[i][j][1]);
}
}
llong ans = 0ll;
for(int i=0; i<=sum; i++) ans = (ans+dp[n][i][0])%P;
printf("%lld
",ans);
return 0;
}