题目链接
https://loj.ac/problem/2731
题解
首先一个很自然的思路是，设\(dp[i][j]\)表示选了前\(i\)列，第\(2\)行第\(i\)列的格子是第\(j\)个被填上的。
还要加个第三维\(0/1\)，表示第\(2\)行第\(i\)列不是/是这一列最后一个被填上的（这决定了它是被上下填上还是被左右填上）。
转移: 若第\(2\)行第\(i\)列是棋子，则所有的都转移到\(f[i][0][0]\).
(1) \(0\rightarrow 0\), 两个互不影响，可以从任意的\(j'\)的\(f[i][j'][0]\)转移过来，组合数选出顺序。
(2) \(1\rightarrow 0\), \((2,i)\)要在\((2,i-1)\)之前选，可以从大于当前的\(j'\)转移过来，同样用组合数选出顺序。
(3) \(0\rightarrow 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)\n",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\n",ans);return 0;
}
