import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC53236. 棋盘游戏
描述
输入描述
第一行有一个整数N,表示棋盘的大小为纵向3格,横向N格。
接下来的三行均为仅由o和x组成的字符串。这三行中第i行的第j个字符表示棋盘中从上到下第i行,从左到右第j个棋子的状态。其中o表示开始时有棋子被放置,x表示开始时这个位置为没有放置着棋子。
输出描述
一个整数,表示符合条件的方案个数。
示例1
输入:
3 oxo xxo oxo
输出:
14
说明:
对于样例1,游戏的初始状态如下图所示(用◯表示有棋子放置):示例2
输入:
10 ooxooxoxoo xooxxxoxxx oxoxoooooo
输出:
149022720
示例3
输入:
10 ooxoxxoxoo oxxxxxoxxx oxooxoxoxo
输出:
0
说明:
没有可以达到最终状态的方案。示例4
输入:
20 oxooxoxooxoxooxoxoxo oxxxoxoxxxooxxxxxoox oxooxoxooxooxooxoxoo
输出:
228518545
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 2005using 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;}