LOJ 2731 「JOISC 2016 Day 1」棋盘游戏

solutions

一张 $3 \times n$ 棋盘，每个格子上放置了 $0/1$ 个棋子，你可以选择一个上下或左右均有棋子的位置放置棋子，最后放满整个棋盘，求放置的方案数，对 $10^9 + 7$ 取模。

$1 \le n \le 2 \times 10^3$。

考虑什么样的棋盘可以放满，四个角必须有棋子，第一行和第三行只能通过左右有棋子的方式放置，那么不能有两个连续的空位。易证这是充要的。先判断，不能放满输出 $0$。

第一行和第三行的空位可以在任意时刻放置，只需考虑中间的空位。对于中间有棋子的，它的左右两边是独立的，分开计算最后计算排列即可，所以只需考虑中间都是空的连续段。

显然要 DP，考虑记录中间的空位放置的时刻和放置方式，记 $f(i,j,0/1)$ 为枚举到第 $i$ 列，中间的空位在 $j$ 时放置，放置方式为上下/左右。

转移有 $0 \gets 0,0 \gets 1,1 \gets 0$ 三种情况，记 $c$ 为第 $i$ 列上下的空格数，$cnt_i$ 为 $i$ 列及以前的空格数，为不算重强制能上下放就上下放。

其中第三种情况的思考方式是先放入中间的空格，再放入上下的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;

const int N=2e3+10,INF=1e9,MOD=1e9+7;
inline void mod(int &x){ if(x>=MOD) x-=MOD; if(x<0) x+=MOD; }
inline int qm(int x,int y=MOD-2){ int res=1; for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD; return res; }
#define gc getchar()
#define rd read()
inline int read(){
    int x=0,f=0; char c=gc;
    for(;c<'0'||c>'9';c=gc) f|=(c=='-');
    for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

int jc[N*3],fjc[N*3];
inline void _init(int n){
    jc[0]=1; for(int i=1;i<=n;++i) jc[i]=1ll*jc[i-1]*i%MOD;
    fjc[n]=qm(jc[n]); for(int i=n-1;~i;--i) fjc[i]=1ll*fjc[i+1]*(i+1)%MOD;
}
inline int C(int n,int m){ return m>n||n<0||m<0?0:1ll*jc[n]*fjc[m]%MOD*fjc[n-m]%MOD; }
inline int P(int n,int m){ return m>n||n<0||m<0?0:1ll*jc[n]*fjc[n-m]%MOD; }

int n,all=0,f[N*3][2],g[N*3][2],ans=1,cnt=0; char s[3][N];
inline int chk(){
    if(s[0][1]=='x'||s[2][1]=='x'||s[0][n]=='x'||s[2][n]=='x') return 0;
    for(int i=1;i<n;++i){
        if(s[0][i]=='x'&&s[0][i+1]=='x') return 0;
        if(s[2][i]=='x'&&s[2][i+1]=='x') return 0;
    }
    return 1;
}

void init(int i){
    all=(s[0][i]=='x')+(s[2][i]=='x')+1;
    for(int j=1;j<=all;++j) f[j][0]=f[j][1]=0;
    f[all][0]=jc[all-1];
    for(int i=1;i<all;++i) f[i][1]=jc[all-1];
    for(int j=1;j<=all;++j) mod(g[j][0]=g[j-1][0]+f[j][0]),mod(g[j][1]=g[j-1][1]+f[j][1]);
}
void get(int i){
    int c=(s[0][i]=='x')+(s[2][i]=='x'); all+=c+1;
    for(int j=1;j<=all;++j) f[j][0]=f[j][1]=0;
    for(int j=c+1;j<=all;++j) mod(f[j][0]+=1ll*P(j-1,c)*g[all-c-1][0]%MOD);
    for(int j=c+1;j<=all;++j) mod(f[j][0]+=1ll*P(j-1,c)*(g[all-c-1][1]-g[j-c-1][1])%MOD);
    for(int x=0;x<c;++x) for(int j=1;j<=all-c;++j) mod(f[j+x][1]+=1ll*jc[c]*C(j+x-1,j-1)%MOD*C(all-j-x,c-x)%MOD*g[j-1][0]%MOD);
    for(int j=1;j<=all;++j) mod(g[j][0]=g[j-1][0]+f[j][0]),mod(g[j][1]=g[j-1][1]+f[j][1]);
}

int main(){

    n=rd,scanf("%s %s %s", s[0]+1, s[1]+1, s[2]+1);
    if(!chk()) return printf("0\n"),0; _init(n*3);

    for(int i=1,j;i<=n;i=j){
        if(s[1][i]=='o') cnt+=(s[0][i]=='x')+(s[2][i]=='x'),j=i+1;
        else{
            for(j=i;j<=n&&s[1][j]==s[1][i];++j);
            init(i); for(int k=i+1;k<j;++k) get(k);
            ans=1ll*(g[all][0]+g[all][1])%MOD*ans%MOD*fjc[all]%MOD,cnt+=all;
        }
    }
    ans=1ll*ans*jc[cnt]%MOD;

    printf("%d\n", ans);

    return 0;
}