[loj2731]「JOISC 2016 Day 1」棋盘游戏

题目大意

有一个3 × n的棋盘,你在上面玩游戏。开始时,棋盘有一些格子上已经摆上了棋子,剩下的格子都是空的。每次你可以选择一个空的格子摆上棋子,这个格子必须满足以下两个条件之一:

1. 这个格子上下两格都有棋子;
2. 这个格子左右两格都有棋子。
   你想知道有多少种不同的摆满棋盘的摆放顺序。

思路

首先判断无解,如果四个角没有棋子或者一三行出现了连续两个空格子,那么就无解.

然后发现整个图变成了这个样子:

oxoxoxoxo
xxxxoxxxo
oxoxoxoxo

我们发现一三行的格子任意时刻都可以放上棋子,只有中间一行的棋子我们需要考虑先后顺序.

考虑根据中间那一行的连通性来划分联通块,每一个块之间可以独立计算,不互相影响.

然后对于每一个块,我们考虑对最后的摆放的位置序列进行dp,每次将一个列的元素添加到序列中,不难发现对于每一列中间的元素,我们有两种方式将它加入进去:

1. 上下都有棋子
2. 左右都有棋子

为了不算重,我们将两者都满足的情况算成第一种,对于第一种情况的转移,不难发现和旁边两列摆放的位置没有任意影响,但是对于第二种,我们要求旁边两列的棋子均摆放在这一列的前面.

于是设状态f[i][j][0/1]表示第i列的中间那个棋子是第j个加进序列,且是通过第1/2种方案加进去的.

直接转移是 n 3 n^3 n3的,可以用前缀和优化至 n 2 n^2 n2.

/*=======================================* Author : ylsoi* Time : 2019.2.26* Problem : game* E-mail : ylsoi@foxmail.com* ====================================*/
#include#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<
#define fi first
#define se second
#define mk make_pair
#define pb push_back
typedef long long ll;using namespace std;void File(){freopen("game.in","r",stdin);freopen("game.out","w",stdout);
}template<typename T>void read(T &_){_=0; T f=1; char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())_=(_<<1)+(_<<3)+(c^'0');_*=f;
}const int maxn=2000+10;
const int mod=1e9+7;
int n,f[maxn][maxn*3][2];
char s[4][maxn];
int fac[maxn*3],ifac[maxn*3];void inc(int &x,int y){(x+=y)>=mod ? x-=mod : x<0 ? x+=mod : 0;}int qpow(int x,int y){int ret=1; x%=mod;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;
}void math_init(){fac[0]=1;REP(i,1,6000)fac[i]=1ll*fac[i-1]*i%mod;ifac[6000]=qpow(fac[6000],mod-2);DREP(i,5999,0)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}int C(int x,int y){if(x<0 || y<0 || x<y)return 0;return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}int main(){File();read(n);REP(i,1,3)scanf("%s",s[i]+1);REP(i,1,n){if(s[1][i]=='x' && (i==1 || i==n || s[1][i-1]=='x' || s[1][i+1]=='x'))puts("0"),exit(0);if(s[3][i]=='x' && (i==1 || i==n || s[3][i-1]=='x' || s[3][i+1]=='x'))puts("0"),exit(0);}math_init();int sum=0,now=0,ans=1;if(s[2][1]=='x'){f[1][1][0]=1,now=1;if(n==1 || s[2][2]=='o')sum=1,now=0;}REP(i,2,n){int cur=(s[1][i]=='x')+(s[3][i]=='x');if(s[2][i]=='o'){sum+=cur;ans=1ll*ans*fac[cur]%mod*C(sum,cur)%mod;continue;}++cur;now+=cur;REP(j,1,now){int per=fac[cur-1];if(now==cur){if(j==cur)f[i][j][0]=per;if(i<n && j!=cur)f[i][j][1]=per;}else{inc(f[i][j][0],1ll*f[i-1][now-cur][0]*per%mod*C(j-1,cur-1)%mod);inc(f[i][j][0],1ll*(f[i-1][now-cur][1]-f[i-1][max(j-cur,0)][1])*per%mod*C(j-1,cur-1)%mod);if(i<n){if(cur==2)inc(f[i][j][1],1ll*f[i-1][min(now-cur,j-1)][0]*per%mod*(now-j)%mod);if(cur==3){inc(f[i][j][1],1ll*f[i-1][min(now-cur,j-1)][0]*per%mod*C(now-j,2)%mod);inc(f[i][j][1],1ll*f[i-1][max(j-2,0)][0]*per%mod*(j-1)%mod*(now-j)%mod);}}}}if(i==n || s[2][i+1]=='o'){sum+=now;int ts=0;REP(j,1,now)inc(ts,(f[i][j][0]+f[i][j][1]*(i<n))%mod);ans=1ll*ans*ts%mod*C(sum,now)%mod;now=0;}REP(j,1,now){inc(f[i][j][0],f[i][j-1][0]);inc(f[i][j][1],f[i][j-1][1]);}}printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！