| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 781664 |
2023-07-13T09:29:25 Z |
박영우(#10014) |
None (JOI16_solitaire) |
C++17 |
|
23 ms |
42812 KB |
#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];
int fact[MAX * 3];
ll dp[2][MAX][MAX];
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 + 3] += (C[j + num[i]][num[i]] * fact[num[i]] * psum) % MOD;
dp[1][i][j + 3] += (C[j + num[i]][num[i]] * fact[num[i]] * psum) % MOD;
dp[0][i][j + 3] %= MOD;
dp[1][i][j + 3] %= MOD;
}
psum = 0;
for (j = 1; j <= sum; j++) {
psum += dp[1][i - 1][j];
psum %= MOD;
dp[0][i][j + 3] += (C[j + num[i]][num[i]] * fact[num[i]] * psum) % MOD; //both down
dp[1][i][j + 3] += (C[j + num[i]][num[i]] * fact[num[i]] * psum) % MOD;
if (num[i] == 2) {
dp[0][i][j + 1] += (C[sum - j + 2][2] * 2 * psum) % MOD; //both up
dp[0][i][j + 2] += ((((sum - j + 1ll) * (j + 1ll)) % MOD) * 2 * psum) % MOD; //up down
}
if (num[i] == 1) dp[0][i][j + 1] += (C[sum - j + 1][2] * 2 * psum) % MOD; //both up
dp[0][i][j + 1] %= MOD;
dp[0][i][j + 2] %= MOD;
dp[0][i][j + 3] %= MOD;
dp[1][i][j + 3] %= 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;
}
ans *= fact[all];
ans %= MOD;
ans *= fact[cnt];
ans %= MOD;
ans *= C[cnt + all][cnt];
ans %= MOD;
cout << ans << ln;
}
Compilation message
solitaire.cpp: In function 'int main()':
solitaire.cpp:126:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
42812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
