「JOISC 2016 Day 1」棋盘游戏

先判无解：第1,3行有连续的空格或四个角有空格。

然后可以发现有解的情况第1,3行可以在任意时间摆放。

对于某一列，若第2行放有棋子，那么显然可以把棋盘分开两边来计算，然后再排列一下。

所以目前要处理的是一段 第二行都没有棋子的棋盘的方案数。

对于该段棋盘：

定义\(dp[i][j][2]\)为前\(i\)列，当前列的第二行是第\(j\)个放置的，\(0/1\)表示是否为通过行的方式放置。

这里为了避免重复和方便，若可以通过列的方式放置，就不通过行的方式放置。

具体的转移相当于前\(i-1\)列放置棋子的顺序序列中插入第\(i\)列的放置顺序。

第一列在dp前处理掉。

转移就分为3种（显然两列不能同时通过行的方式放置）。

令v为\(i\)列中1,3行没放置棋子格子数。

以T来指代\(i\)列第二行的棋子，\(T_1\)为\(i-1\)列第二行棋子。

0->0

只需要保证在放T前放好v。

0->1

要保证在放T后才放好v，\(T_1\)在T前放。

1->0

保证在放T前放好v，放T在\(T_1\)前。

整个棋盘的第一和最后一列都是不用特判的，因为它们都是列放置。

对于其他整段，第一列的第二行前面和最后一列的第二行后面都是有棋子的。

#include<bits/stdc++.h>
#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)
#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)
#define mem(a,b) memset(a,b,sizeof a )
#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl
using namespace std;
void in(int &r) {
    static char c;
    r=0;
    while(c=getchar(),!isdigit(c));
    do r=(r<<1)+(r<<3)+(c^48);
    while(c=getchar(),isdigit(c));
}
const int mn=2005;
int dp[mn][mn*3][2];
int had[mn][4],n;//其实这里had是没有的意思，没有改过来
const int mod=1e9+7;
int mul[mn*3],inv[mn*3];
int C(int a,int b){
    return 1LL*mul[b]*inv[a]%mod*inv[b-a]%mod;
}
int A(int a,int b){
    return 1LL*mul[b]*inv[b-a]%mod;
}
int tot_sum,ans=1;
void add(int &a,long long b){
    a=(a+b)%mod;
}
int Sum[mn*3][2];
void get_ans(int l,int r){
    if(l>r)return;
    int sum=0;
    int v=had[l][1]+had[l][3];
    dp[l][v+1][0]=A(v,v);
    rep(q,1,v)dp[l][q][1]=A(v,v);
    sum+=v+1;
    
    rep(q,l+1,r){
        v=had[q][1]+had[q][3];
        rep(w,1,sum)Sum[w][0]=dp[q-1][w][0],Sum[w][1]=dp[q-1][w][1];
        rep(w,1,sum)add(Sum[w][0],Sum[w-1][0]),add(Sum[w][1],Sum[w-1][1]);
        rep(w,v+1,sum+v+1){
            add(dp[q][w][0],1LL*A(v,w-1)*Sum[sum][0]);
//          rep(e,1,sum){
//              add(dp[q][w][0],1LL*A(v,w-1)*dp[q-1][e][0]);
//          }
        }
        rep(w,v+1,sum+v){
            add(dp[q][w][0],1LL*A(v,w-1)*(Sum[sum][1]-Sum[w-v-1][1]));
//          rep(e,w-v,sum){
//              add(dp[q][w][0],1LL*A(v,w-1)*dp[q-1][e][1]);
//          }
        }
        rep(r,0,v-1){
            int ty=C(r,v);
            rep(w,r+1,sum+r+1){
                add(dp[q][w][1],1LL*ty*A(r,w-1)*A(v-r,sum+v+1-w)%mod*Sum[w-r-1][0]);
//              rep(e,0,w-r-1){
//                  add(dp[q][w][1],1LL*ty*A(r,w-1)*dp[q-1][e][0]%mod*A(v-r,sum+v+1-w));
//              }
            }
        }
        sum+=v+1;
    }
    
    int tot=0;
    rep(q,0,sum){
        add(tot,dp[r][q][0]);
        add(tot,dp[r][q][1]);
    }
    tot_sum+=sum,ans=1LL*ans*tot%mod*C(sum,tot_sum)%mod;
}
bool check_it_can_be_solve(){
    if(had[1][1]||had[1][3]||had[n][1]||had[n][3])return 0;
    rep(q,2,n)if(had[q][1]&&had[q-1][1]||had[q][3]&&had[q-1][3])return 0;
    return 1;
}
char as[mn];
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    in(n);
    mul[0]=1;
    rep(q,1,n*3)mul[q]=1LL*mul[q-1]*q%mod;
    inv[0]=inv[1]=1;
    rep(q,2,n*3)inv[q]=1LL*(mod-mod/q)*inv[mod%q]%mod;
    rep(q,1,n*3)inv[q]=1LL*inv[q-1]*inv[q]%mod;
    rep(q,1,3){
        scanf("%s",as+1);
        rep(w,1,n)had[w][q]=as[w]=='x';
    }
    if(!check_it_can_be_solve()){
        puts("0");
        return 0;
    }
    int now=1;
    while(now<=n&&had[now][2])++now;
    if(now==n+1)get_ans(1,now-1);
    else{
        get_ans(1,now-1);
        int v=had[now][1]+had[now][3];
        tot_sum+=v,ans=1LL*ans*A(v,tot_sum)%mod;
        ++now;
        while(1){
            int last=now;
            while(now<=n&&had[now][2])++now;
            if(now==n+1)get_ans(last,now-1);
            else{
                get_ans(last,now-1);
                v=had[now][1]+had[now][3];
                tot_sum+=v,ans=1LL*ans*A(v,tot_sum)%mod;
                ++now;
            }
            if(now==n+1)break;
        }
    }
    printf("%d\n",(ans+mod)%mod);
    return 0;
}