棋盘游戏

C++11(clang++ 3.9) 解法, 执行用时: 144ms, 内存消耗: 69456K, 提交时间: 2020-08-11 21:29:35
#include<bits/stdc++.h>
#define ll long long
#define pr pair<int,int>
#define mp(a,b) make_pair(a,b)
#define N 2005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=1e9+7;
ll ksm(ll t,ll x) {
    ll ans=1;
    for(;x;x>>=1,t=t*t%mod)
        if(x&1) ans=ans*t%mod;
    return ans;
}
int n;
char mp[4][N];
ll fac[N*3],ifac[N*3];
ll C(int n,int m) {
    if(n<m) return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int u[N];
ll f[N][N*3],g[N][N*3];
int res,sum[N];
ll pre[N*3];
int main() {
    n=Get();
    fac[0]=1;
    for(int i=1;i<=3*n;i++) fac[i]=fac[i-1]*i%mod;
    ifac[3*n]=ksm(fac[3*n],mod-2);
    for(int i=3*n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    for(int i=1;i<=3;i++) {
        scanf("%s",mp[i]+1);
    }
    
    for(int i=1;i<=n;i++) {
        if(mp[1][i]=='x'&&(mp[1][i-1]!='o'||mp[1][i+1]!='o')) {cout<<0;return 0;}
        if(mp[3][i]=='x'&&(mp[3][i-1]!='o'||mp[3][i+1]!='o')) {cout<<0;return 0;}
    }
    
    for(int i=1;i<=n;i++) {
        if(mp[1][i]=='x') u[i]++;
        if(mp[3][i]=='x') u[i]++;
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+u[i]+(mp[2][i]=='x');
    
    
    if(mp[2][1]=='x') f[1][1]=1;
    else f[1][0]=1;
    for(int i=2;i<=n;i++) {
        if(mp[2][i]=='x') {
            if(mp[2][i-1]=='x') {
                memset(pre,0,sizeof(pre));
                for(int j=1;j<=sum[i-1];j++) {//f,i-1由上下贡献 
                    if(u[i-1]==2) pre[j]=(pre[j-1]+f[i-1][j]*j%mod*(j+1))%mod;
                    else if(u[i-1]==1) pre[j]=(pre[j-1]+f[i-1][j]*j)%mod;
                    else pre[j]=(pre[j-1]+f[i-1][j])%mod;
                }
                
                for(int j=sum[i-1];j>=1;j--) if(j>u[i-1]) pre[j]=pre[j-u[i-1]];
                for(int j=1;j<=u[i-1];j++) pre[j]=0;
                
                for(int j=1;j<=sum[i-1];j++) (f[i][j]+=pre[sum[i-1]]-pre[j-1]+mod)%=mod;
                for(int j=2;j<=sum[i-1]+1;j++) (g[i][j]+=pre[j-1])%=mod;
                
                memset(pre,0,sizeof(pre));
                for(int j=1;j<=sum[i-1];j++) {//g,i-1由上下贡献 
                    if(u[i-1]==2) pre[j]=(pre[j-1]+g[i-1][j]*j%mod*(j+1))%mod;
                    else if(u[i-1]==1) pre[j]=(pre[j-1]+g[i-1][j]*j)%mod;
                    else pre[j]=(pre[j-1]+g[i-1][j])%mod;
                }
                
                for(int j=sum[i-1];j>=1;j--) if(j>u[i-1]) pre[j]=pre[j-u[i-1]];
                for(int j=1;j<=u[i-1];j++) pre[j]=0;
                for(int j=2;j<=sum[i-1]+1;j++) (g[i][j]+=pre[j-1])%=mod;
                
                memset(pre,0,sizeof(pre));
                for(int j=1;j<=sum[i-1];j++) {//g,i-1由左右贡献 
                    (pre[j]+=pre[j-1])%=mod;
                    if(!u[i-1]) {
                        (pre[j]+=g[i-1][j])%=mod;
                    } else if(u[i-1]==1) {
                        (pre[j+1]+=g[i-1][j]*j)%=mod;
                        (pre[j]+=g[i-1][j]*(sum[i-1]-j))%=mod;
                    } else {
                        (pre[j]+=g[i-1][j]*(sum[i-1]-j-1)%mod*(sum[i-1]-j))%=mod;
                        (pre[j+1]+=g[i-1][j]*j%mod*(sum[i-1]-j-1)%mod*2)%=mod;
                        (pre[j+2]+=g[i-1][j]*j%mod*(j+1))%=mod;
                    }
                }
                for(int j=1;j<=sum[i-1];j++) (f[i][j]+=pre[sum[i-1]]-pre[j-1]+mod)%=mod;
            } else {
                for(int j=1;j<=sum[i-1]+1;j++) {
                    if(u[i-1]==0) g[i][j]=f[i-1][0];
                    else if(u[i-1]==1) g[i][j]=f[i-1][0]*sum[i-1]%mod;
                    else g[i][j]=f[i-1][0]*(sum[i-1]-1)%mod*sum[i-1]%mod;
                }
            }
        } else {
            if(mp[2][i-1]=='x') {
                for(int j=1;j<=sum[i-1];j++) {
                    if(u[i-1]==0) {
                        (f[i][0]+=f[i-1][j]+g[i-1][j])%=mod;
                    } else if(u[i-1]==1) {
                        (f[i][0]+=f[i-1][j]*j+g[i-1][j]*(sum[i-1]))%=mod;
                    } else {
                        (f[i][0]+=f[i-1][j]*j%mod*(j+1)+g[i-1][j]*(sum[i-1])%mod*(sum[i-1]-1))%=mod;
                    }
                }
            } else {
                if(u[i-1]==0) f[i][0]=f[i-1][0];
                else if(u[i-1]==1) f[i][0]=f[i-1][0]*sum[i-1]%mod;
                else f[i][0]=f[i-1][0]*(sum[i-1]-1)%mod*sum[i-1]%mod;
            }
        }
    }
    ll ans=0;
    if(mp[2][n]=='o') {
        if(!u[n]) (ans+=(f[n][0]))%=mod;
        else if(u[n]==1) (ans+=f[n][0]*sum[n])%=mod;
        else (ans+=f[n][0]*(sum[n]-1)%mod*sum[n])%=mod;
    } else {
        for(int i=1;i<=sum[n];i++) {
            if(!u[n]) (ans+=(f[n][i]+g[n][i]))%=mod;
            else if(u[n]==1) (ans+=f[n][i]*i+g[n][i]*sum[n])%=mod;
            else (ans+=f[n][i]*i%mod*(i-1)+g[n][i]*sum[n]%mod*(sum[n]-1))%=mod;
        }
    }
    cout<<ans;
    return 0;
}
详情
