| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117925 |
2019-06-17T12:44:52 Z |
sebinkim |
None (JOI16_solitaire) |
C++14 |
|
13 ms |
5760 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
char A[2020], B[2020], C[2020];
ll dp[2020][6060], S[2020];
ll X1[6060], X2[6060], X3[6060], Y[6060];
ll n, ans;
void die() { printf("0\n"); exit(0); }
int main()
{
ll i, j, k, x, s, s1, s2, t1, t2;
ll l1, l2, y;
scanf("%lld%s%s%s", &n, A + 1, B + 1, C + 1);
if(A[1] == 'x' || A[n] == 'x') die();
if(C[1] == 'x' || C[n] == 'x') die();
for(i=1; i<n; i++){
if(A[i] == 'x' && A[i + 1] == 'x') die();
if(C[i] == 'x' && C[i + 1] == 'x') die();
}
dp[0][0] = 1;
for(i=1; i<=n; i++){
S[i] = S[i - 1] + (A[i] == 'x') + (B[i] == 'x') + (C[i] == 'x');
s = S[i];
if(B[i] == 'o'){
if(A[i] == 'x' && C[i] == 'x') t1 = 0;
else if(A[i] == 'x' || C[i] == 'x') t1 = 1;
else t1 = 2;
for(k=0; k<=s; k++){
if(t1 == 0) dp[i][0] = (dp[i][0] + dp[i - 1][k] * s * (s - 1)) % mod;
else if(t1 == 1) dp[i][0] = (dp[i][0] + dp[i - 1][k] * s) % mod;
else dp[i][0] = (dp[i][0] + dp[i - 1][k]) % mod;
}
if(B[i - 1] == 'o' || i < 3) continue;
s2 = S[i - 2];
if(A[i - 1] == 'x' && C[i - 1] == 'x') t2 = 0;
else if(A[i - 1] == 'x' || C[i - 1] == 'x') t2 = 1;
else t2 = 2;
for(k=0; k<=s; k++){
if(t2 == 0){
x = k * (s2 - k + 2) * (s2 - k + 1) / 2 * 2 % mod;
x = (x + (s2 - k + 3) * (s2 - k + 2) * (s2 - k + 1) / 6 * 4) % mod;
}
else if(t2 == 1) x = (s2 - k + 2) * (s2 - k + 1) / 2 % mod;
else x = 0;
x = x * dp[i - 2][k] % mod;
if(t1 == 0) dp[i][0] = (dp[i][0] + x * s * (s - 1)) % mod;
else if(t1 == 1) dp[i][0] = (dp[i][0] + x * s) % mod;
else dp[i][0] = (dp[i][0] + x) % mod;
}
}
else{
if(A[i] == 'x' && C[i] == 'x') t1 = 0;
else if(A[i] == 'x' || C[i] == 'x') t1 = 1;
else t1 = 2;
y = 0;
for(k=0; k<=s; k++){
y = (y + dp[i - 1][k]) % mod;
}
for(j=1; j<=s; j++){
if(t1 == 0) dp[i][j] = (dp[i][j] + y * (j - 1) * (j - 2)) % mod;
else if(t1 == 1) dp[i][j] = (dp[i][j] + y * (j - 1)) % mod;
else dp[i][j] = (dp[i][j] + y) % mod;
}
if(B[i - 1] == 'o' || i < 3) continue;
s2 = S[i - 2];
s1 = s2 + S[i] - S[i - 1];
if(A[i - 1] == 'x' && C[i - 1] == 'x') t2 = 0;
else if(A[i - 1] == 'x' || C[i - 1] == 'x') t2 = 1;
else t2 = 2;
X1[s + 1] = X2[s + 1] = X3[s + 1] = 0;
for(k=s; k>=0; k--){
X1[k] = (X1[k + 1] + dp[i - 2][k] * (s1 - k + t1) % mod * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 6 * 4) % mod;
X2[k] = (X2[k + 1] + dp[i - 2][k] * (k + 3 - t1) % mod * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 2 * 2) % mod;
X3[k] = (X3[k + 1] + dp[i - 2][k] * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 2) % mod;
}
Y[0] = dp[i - 2][0];
for(k=1; k<=s; k++){
Y[k] = (Y[k - 1] + dp[i - 2][k]) % mod;
}
for(j=1; j<=s; j++){
if(t1 == 0) x = (j - 1) * (j - 2) % mod;
else if(t1 == 1) x = (j - 1) % mod;
else x = 1;
l1 = max(j + t1 - 2, 0ll);
l2 = max(l1 - 1, 0ll);
if(t2 == 0){
dp[i][j] = (dp[i][j] + x * X1[l1]) % mod;
dp[i][j] = (dp[i][j] + x * X2[l1] - j * x * X3[l1] * 2) % mod;
dp[i][j + 1] = (dp[i][j + 1] + x * j * X3[l1] * 2) % mod;
dp[i][j] = (dp[i][j] + x * Y[l2] * (s1 - j + 3) % mod * (s1 - j + 2) * (s1 - j + 1) / 6 * 4) % mod;
dp[i][j + 1] = (dp[i][j + 1] + x * Y[l2] * j % mod * (s1 - j + 2) * (s1 - j + 1) / 2 * 2) % mod;
}
else if(t2 == 1){
dp[i][j] = (dp[i][j] + x * X3[l1]) % mod;
dp[i][j] = (dp[i][j] + x * Y[l2] * (s1 - j + 2) % mod * (s1 - j + 1) / 2) % mod;
}
}
dp[i][s + 1] = 0;
}
}
s = S[n];
for(i=0; i<=s; i++){
ans = (ans + dp[n][i]) % mod;
}
ans = (ans + mod) % mod;
printf("%lld\n", ans);
return 0;
}
Compilation message
solitaire.cpp: In function 'int main()':
solitaire.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%s%s%s", &n, A + 1, B + 1, C + 1);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
5760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
