Submission #365446

#	Time	Username	Problem	Language	Result	Execution time	Memory
365446		arnold518	Solitaire (JOI16_solitaire)	C++14	100 / 100	237 ms	69484 KiB

solitaire

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 6000;
const ll MOD = 1e9+7;

int N, cnt;
char S[4][MAXN+10];
int A[4][MAXN+10];
int B[MAXN+10];
ll fac[MAXN+10], ifac[MAXN+10];

ll ans;
ll dp1[MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10];

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll t=mypow(x, y/2);
	return t*t%MOD;
}

ll inv(ll x)
{
	return mypow(x, MOD-2);
}

ll ncr(ll n, ll r)
{
	if(n<r) return 0;
	return fac[n]*ifac[r]%MOD*ifac[n-r]%MOD;
}

ll npr(ll n, ll r)
{
	if(n<r) return 0;
	return fac[n]*ifac[n-r]%MOD;
}

int main()
{
	fac[0]=1; ifac[0]=1;
	for(int i=1; i<=MAXN; i++) fac[i]=fac[i-1]*i%MOD;
	for(int i=1; i<=MAXN; i++) ifac[i]=inv(fac[i]);

	scanf("%d", &N);
	scanf(" %s", S[1]+1);
	scanf(" %s", S[2]+1);
	scanf(" %s", S[3]+1);
	for(int i=1; i<=N; i++)
	{
		A[1][i]=(S[1][i]=='x');
		A[2][i]=(S[2][i]=='x');
		A[3][i]=(S[3][i]=='x');
	}

	A[1][0]=1; A[1][N+1]=1;
	A[2][0]=1; A[2][N+1]=1;
	A[3][0]=1; A[3][N+1]=1;
	for(int i=1; i<=N; i++)
	{
		if(A[1][i])
		{
			if(A[1][i-1] || A[1][i+1])
			{
				return !printf("0\n");
			}
		}
	}
	for(int i=1; i<=N; i++)
	{
		if(A[3][i])
		{
			if(A[3][i-1] || A[3][i+1])
			{
				return !printf("0\n");
			}
		}
	}

	int cnt=0;
	for(int i=1; i<=N; i++)
	{
		if(A[2][i]==0)
		{
			B[i]=-1;
			cnt+=A[1][i]+A[3][i];
		}
		else
		{
			B[i]=A[1][i]+A[3][i];
		}
	}

	int sz=0;
	vector<ll> V;
	vector<int> VV;
	VV.push_back(0);
	for(int i=1; i<=N; i++) if(B[i]==-1) VV.push_back(i);
	VV.push_back(N+1);
	
	sz=cnt;
	ans=fac[cnt];
	for(int i=0; i+1<VV.size(); i++)
	{
		int l=VV[i]+1, r=VV[i+1]-1;
		if(l>r) continue;

		int val=0;
		for(int j=1; j<=B[l]; j++) dp1[l][j]=fac[B[l]];
		dp2[l][B[l]+1]=fac[B[l]];
		val+=B[l]+1;
		for(int k=2; k<=val; k++)
		{
			dp1[l][k]+=dp1[l][k-1];
			dp1[l][k]%=MOD;
			dp2[l][k]+=dp2[l][k-1];
			dp2[l][k]%=MOD;
		}

		if(l==1)
		{
			for(int j=1; j<=B[l]; j++) dp1[l][j]=0;
		}

		for(int j=l+1; j<=r; j++)
		{
			for(int k=1; k<=val+B[j]+1; k++)
			{
				for(int p=B[j]; p<=B[j]; p++)
				{
					ll t=ncr(B[j], p)*npr(k-1, p)%MOD*npr(val+B[j]+1-k, B[j]-p)%MOD;
					dp2[j][k]+=dp2[j-1][val]*t%MOD;
					dp2[j][k]%=MOD;
					ll x=dp1[j-1][val]-dp1[j-1][k-p-1];
					x%=MOD;
					if(x<0) x+=MOD;
					dp2[j][k]+=x*t%MOD;
					dp2[j][k]%=MOD;
				}
				for(int p=0; p<B[j]; p++)
				{
					ll t=ncr(B[j], p)*npr(k-1, p)%MOD*npr(val+B[j]+1-k, B[j]-p)%MOD;
					dp1[j][k]+=dp2[j-1][k-p-1]*t%MOD;
					dp1[j][k]%=MOD;
				}
			}

			val+=B[j]+1;
			for(int k=2; k<=val; k++)
			{
				dp1[j][k]+=dp1[j][k-1];
				dp1[j][k]%=MOD;
				dp2[j][k]+=dp2[j][k-1];
				dp2[j][k]%=MOD;
			}
		}

		ll t=0;
		if(r!=N)
		{
			t+=dp1[r][val];
			t%=MOD;
		}
		t+=dp2[r][val];
		t%=MOD;
		ans=ans*ncr(sz+val, sz)%MOD*t%MOD;
		sz+=val;
	}

	printf("%lld\n", ans);
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for(int i=0; i+1<VV.size(); i++)
      |               ~~~^~~~~~~~~~
solitaire.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
solitaire.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf(" %s", S[1]+1);
      |  ~~~~~^~~~~~~~~~~~~~~
solitaire.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf(" %s", S[2]+1);
      |  ~~~~~^~~~~~~~~~~~~~~
solitaire.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf(" %s", S[3]+1);
      |  ~~~~~^~~~~~~~~~~~~~~

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