Submission #781786

#	Time	Username	Problem	Language	Result	Execution time	Memory
781786		flappybird	Solitaire (JOI16_solitaire)	C++17	100 / 100	223 ms	234092 KiB

solitaire

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2020
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
ll C[MAX * 3][MAX * 3];
int arr[3][MAX];
ll fact[MAX * 3];
ll dp[2][MAX][MAX * 3];
int num[MAX];
void no() {
	cout << 0;
	exit(0);
}
ll mpow(ll x, ll y = MOD - 2) {
	if (!y) return 1;
	ll res = mpow(x, y / 2);
	res *= res;
	res %= MOD;
	if (y & 1) res *= x, res %= MOD;
	return res;
}
ll solve(int l, int r) {
	if (l > r) return 1;
	int i, j;
	if (num[l] == 0) {
		dp[0][l][1] = 1;
		dp[1][l][1] = 1;
	}
	if (num[l] == 1) {
		dp[1][l][2] = 1;
		dp[0][l][1] = 1;
		dp[0][l][2] = 1;
	}
	if (num[l] == 2) {
		dp[1][l][3] = 2;
		dp[0][l][1] = 2;
		dp[0][l][2] = 2;
		dp[0][l][3] = 2;
	}
	ll sum = num[l] + 1;
	for (i = l + 1; i <= r; i++) {
		ll psum = 0;
		for (j = sum - 1; j >= 0; j--) {
			psum += dp[0][i - 1][j + 1];
			psum %= MOD;
			dp[0][i][j + num[i] + 1] += (((C[j + num[i]][num[i]] * fact[num[i]]) % MOD) * psum) % MOD;
			dp[1][i][j + num[i] + 1] += (((C[j + num[i]][num[i]] * fact[num[i]]) % MOD) * psum) % MOD;
			dp[0][i][j + num[i] + 1] %= MOD;
			dp[1][i][j + num[i] + 1] %= MOD;
		}
		psum = 0;
		for (j = 1; j <= sum; j++) {
			psum += dp[1][i - 1][j];
			psum %= MOD;
			dp[0][i][j + num[i] + 1] += (((C[j + num[i]][num[i]] * fact[num[i]]) % MOD) * psum) % MOD; //both down
			dp[1][i][j + num[i] + 1] += (((C[j + num[i]][num[i]] * fact[num[i]]) % MOD) * psum) % MOD;
			dp[0][i][j + num[i] + 1] %= MOD;
			dp[1][i][j + num[i] + 1] %= MOD;
			if (num[i] == 2) {
				dp[0][i][j + 1] += (C[sum - j + 2][2] * 2 * psum) % MOD; //both up
				dp[0][i][j + 1] %= MOD;
				dp[0][i][j + 2] += ((((sum - j + 1ll) * (j + 1ll)) % MOD) * 2 * psum) % MOD; //up down
				dp[0][i][j + 2] %= MOD;
			}
			if (num[i] == 1) {
				dp[0][i][j + 1] += ((sum - j + 1) * psum) % MOD; //both up
				dp[0][i][j + 1] %= MOD;
			}
		}
		sum += num[i] + 1;
	}
	ll res = 0;
	for (i = 1; i <= sum; i++) res += dp[0][r][i], res %= MOD;
	return res;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i, j;
	C[0][0] = 1;
	fact[0] = 1;
	for (i = 1; i <= N * 3 + 10; i++) fact[i] = (fact[i - 1] * i) % MOD;
	for (i = 1; i <= N * 3 + 10; i++) {
		C[i][0] = C[i][i] = 1;
		for (j = 1; j < i; j++) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
			C[i][j] %= MOD;
		}
	}
	string s[3];
	cin >> s[0] >> s[1] >> s[2];
	for (i = 1; i <= N; i++) arr[0][i] = s[0][i - 1] == 'o';
	for (i = 1; i <= N; i++) arr[1][i] = s[1][i - 1] == 'o';
	for (i = 1; i <= N; i++) arr[2][i] = s[2][i - 1] == 'o';
	for (i = 1; i <= N; i++) {
		for (auto c : { 0, 2 }) {
			if (!arr[c][i]) {
				if (!arr[c][i - 1]) no();
				if (!arr[c][i + 1]) no();
			}
		}
	}
	int cnt = 0;
	vector<int> v;
	v.push_back(0);
	for (i = 1; i <= N; i++) {
		num[i] = 2 - arr[0][i] - arr[2][i];
		if (arr[1][i]) {
			cnt += num[i];
			v.push_back(i);
		}
	}
	v.push_back(N + 1);
	ll ans = 1;
	int all = 0;
	for (i = 1; i < v.size(); i++) {
		if (v[i - 1] + 1 > v[i] - 1) continue;
		ans *= solve(v[i - 1] + 1, v[i] - 1);
		ans %= MOD;
		int ccnt = 0;
		for (j = v[i - 1] + 1; j < v[i]; j++) ccnt += 1 + num[j];
		ans *= mpow(fact[ccnt]);
		ans %= MOD;
		all += ccnt;
	}
	all += cnt;
	ans *= fact[all];
	ans %= MOD;
	cout << ans << ln;
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for (i = 1; i < v.size(); i++) {
      |              ~~^~~~~~~~~~

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