제출 #189721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
189721		dndhk	Solitaire (JOI16_solitaire)	C++14	100 / 100	49 ms	904 KiB

solitaire

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 6000;
const ll MOD = 1000000007;

ll multi(ll x, ll y){
	if(y==0)	return 1;
	if(y==1)	return x%MOD;
	ll m = multi(x, y/2);
	if(y%2){
		return (m*m%MOD)*x%MOD;
	}return m*m%MOD;
}

int N;
string str[3];
ll per[MAX_N+1], inv[MAX_N+1];
ll ans = 1, sz = 0;
ll dp[2][MAX_N+1], ndp[2][MAX_N+1];
ll s0[MAX_N+1], s1[MAX_N+1];
int cnt[MAX_N+1];

void input(){
	cin>>N;
	per[0] = per[1] = inv[0] = inv[1] = 1;
	for(int i=2; i<=3*N; i++){
		per[i] = (per[i-1] * (ll)i) % MOD;
		inv[i] = multi(per[i], MOD-2);
	}
	for(int i=0; i<3; i++){
		cin>>str[i];
	}
	
}



int main(){
	input();	
	if(str[0][0]=='x' || str[2][0]=='x' || str[0][N-1]=='x' || str[2][N-1]=='x'){
		printf("0");
		return 0;
	}
	for(int i=0; i<N-1; i++){
		if(str[0][i]=='x' && str[0][i+1]=='x'){
			printf("0");
			return 0;
		}
		if(str[2][i]=='x' && str[2][i+1]=='x'){
			printf("0");
			return 0;
		}
	}
	for(int i=0; i<N; i++){
		if(str[0][i]=='x')	cnt[i]++;
		if(str[2][i]=='x')	cnt[i]++;
	}
	for(int i=0; i<N; i++){
		if(str[1][i]=='x'){
			int s = i, e = i;
			while(e<N-1 && str[1][e+1]=='x')	e++;
			for(int j=0; j<=3*N; j++){
				s0[j] = s1[j] = dp[0][j] = dp[1][j] = ndp[0][j] = ndp[1][j] = 0;
			}
			int l = 0;
			for(int j=s; j<=e; j++){
				if(j==s){
					if(cnt[j]==0){
						ndp[0][1] = ndp[1][1] = 1;
					}else if(cnt[j]==1){
						if(j==0){
							ndp[0][2] = ndp[1][2] = 1;
						}else{
							ndp[0][1] = ndp[0][2] = ndp[1][2] = 1;
						}
					}else{
						if(j==0){
							ndp[0][3] = ndp[1][3] = 2;
						}else{
							ndp[0][1] = ndp[0][2] = ndp[0][3] = 2;
							ndp[1][3] = 2;
						}
					}
				}else{
					if(cnt[j]==0){
						for(int k=1; k<=l+1; k++){
							ndp[0][k] = (s0[k]+s1[k-1])%MOD;
							ndp[1][k] = ndp[0][k];
						}
					}else if(cnt[j]==1){
						for(int k=1; k<=l+2; k++){
							ndp[0][k] = (s0[k-1]*(ll)(k-1)%MOD)+((k>=3?s1[k-2]:0LL)*(ll)(l+1)%MOD) + (dp[1][k-1]*(ll)(l-k+2)%MOD);
							ndp[0][k] = ndp[0][k]%MOD;
							ndp[1][k] = (s0[k-1]+(k>=3?s1[k-2]:0LL))*(ll)(k-1) % MOD;
						}
					}else{
						for(int k=1; k<=l+3; k++){
							if(k>=3)	ndp[1][k] = (((s0[k-2]+s1[k-3])*(ll)(k-1)%MOD)*(ll)(k-2))%MOD;
							if(k>=3){
								//cout<<"*"<<k<<endl;
								ndp[0][k] = ((s0[k-2]*(ll)(k-1)%MOD)*(ll)(k-2))%MOD;
								//cout<<ndp[0][k]<<endl;
								ndp[0][k] = (ndp[0][k] + ((s1[k-3]*(ll)(l+2)%MOD)*(ll)(l+1)%MOD))%MOD;
								//cout<<ndp[0][k]<<endl;
								ndp[0][k] = (ndp[0][k] + (ll)dp[1][k-2] * (((ll)(l+2)*(ll)(l+1) - (ll)(k-2)*(ll)(k-1))%MOD) %MOD)%MOD;
								//cout<<ndp[0][k]<<endl;
							}
							ndp[0][k] = (ndp[0][k] + (dp[1][k-1] * (ll)(l-k+2)%MOD)*(ll)(l-k+3)%MOD)%MOD;
						}
					}
				}
				l+=cnt[j]+1;
				//cout<<"*"<<j<<endl;
				for(int k=1; k<=l; k++){
					dp[0][k] = ndp[0][k];
					dp[1][k] = ndp[1][k];
					//cout<<dp[0][k]<<" "<<dp[1][k]<<endl;
					ndp[0][k] = ndp[1][k] = 0;
				}
				s1[1] = dp[1][1];
				s0[l] = dp[0][l];
				for(int k=2; k<=l; k++){
					s1[k] = s1[k-1]+dp[1][k];
				}
				for(int k=l-1; k>=1; k--){
					s0[k] = s0[k+1]+dp[0][k];
				}
			}
			ll sum = 0;
			for(int k=1; k<=l; k++){
				if(e==N-1){
					sum = (sum + dp[1][k]) % MOD;
				}else{
					sum = (sum + dp[0][k]) % MOD;
				}
			}
			ans = (ans * sum) % MOD;
			ans = (ans * inv[l]) % MOD;
			ans = (ans * inv[sz]) % MOD;
			ans = (ans * per[l+sz]) % MOD;			
			//cout<<"!"<<ans<<" "<<sum<<endl;
			sz+=l;
			i = e;
		}else{
			if(str[0][i]=='x'){
				ans = (ans * (sz+1LL)) % MOD;
				sz++;
			}if(str[2][i]=='x'){
				ans = (ans * (sz+1LL)) % MOD;
				sz++;
			}
		}
	}
	cout<<ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 20 / 20
• Subtask 4: 38 / 38
• Subtask 5: 20 / 20