#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) * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 6 * 4) % mod) % mod;
X2[k] = (X2[k + 1] + dp[i - 2][k] * (k + 3 - t1) % mod * (s1 - k + t1 - 1) * (s1 - k + t1 - 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] % mod * ((s1 - j + 3) * (s1 - j + 2) * (s1 - j + 1) / 6 * 4) % mod) % mod;
dp[i][j + 1] = (dp[i][j + 1] + x * Y[l2] % mod * j * (s1 - j + 2) * (s1 - j + 1)) % mod;
}
else if(t2 == 1){
dp[i][j] = (dp[i][j] + x * X3[l1]) % mod;
dp[i][j] = (dp[i][j] + x * Y[l2] % mod * (s1 - j + 2) * (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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
3 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 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
5760 KB |
Output is correct |
2 |
Correct |
37 ms |
13972 KB |
Output is correct |
3 |
Correct |
9 ms |
4608 KB |
Output is correct |
4 |
Correct |
55 ms |
19232 KB |
Output is correct |
5 |
Correct |
49 ms |
17784 KB |
Output is correct |
6 |
Correct |
46 ms |
16888 KB |
Output is correct |
7 |
Correct |
32 ms |
12564 KB |
Output is correct |
8 |
Correct |
58 ms |
19320 KB |
Output is correct |
9 |
Correct |
59 ms |
19772 KB |
Output is correct |
10 |
Correct |
31 ms |
12152 KB |
Output is correct |
11 |
Correct |
41 ms |
14840 KB |
Output is correct |
12 |
Correct |
98 ms |
19796 KB |
Output is correct |
13 |
Correct |
77 ms |
24184 KB |
Output is correct |
14 |
Correct |
77 ms |
24184 KB |
Output is correct |
15 |
Correct |
77 ms |
24312 KB |
Output is correct |
16 |
Correct |
76 ms |
24184 KB |
Output is correct |
17 |
Correct |
75 ms |
24184 KB |
Output is correct |
18 |
Correct |
77 ms |
24160 KB |
Output is correct |
19 |
Correct |
75 ms |
24184 KB |
Output is correct |
20 |
Correct |
74 ms |
24184 KB |
Output is correct |
21 |
Correct |
78 ms |
24056 KB |
Output is correct |
22 |
Correct |
77 ms |
24148 KB |
Output is correct |
23 |
Correct |
77 ms |
24184 KB |
Output is correct |
24 |
Correct |
78 ms |
24052 KB |
Output is correct |
25 |
Correct |
73 ms |
24076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
2 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
3 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 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
2 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
2 ms |
512 KB |
Output is correct |
23 |
Correct |
3 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
2 ms |
512 KB |
Output is correct |
26 |
Correct |
2 ms |
512 KB |
Output is correct |
27 |
Correct |
2 ms |
512 KB |
Output is correct |
28 |
Correct |
2 ms |
512 KB |
Output is correct |
29 |
Correct |
2 ms |
512 KB |
Output is correct |
30 |
Correct |
2 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
512 KB |
Output is correct |
32 |
Correct |
2 ms |
512 KB |
Output is correct |
33 |
Correct |
2 ms |
512 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
2 ms |
512 KB |
Output is correct |
36 |
Correct |
2 ms |
512 KB |
Output is correct |
37 |
Correct |
2 ms |
768 KB |
Output is correct |
38 |
Correct |
3 ms |
1024 KB |
Output is correct |
39 |
Correct |
4 ms |
512 KB |
Output is correct |
40 |
Correct |
4 ms |
1920 KB |
Output is correct |
41 |
Correct |
3 ms |
1664 KB |
Output is correct |
42 |
Correct |
4 ms |
1792 KB |
Output is correct |
43 |
Correct |
4 ms |
1920 KB |
Output is correct |
44 |
Correct |
4 ms |
1664 KB |
Output is correct |
45 |
Correct |
4 ms |
1792 KB |
Output is correct |
46 |
Correct |
4 ms |
1792 KB |
Output is correct |
47 |
Correct |
4 ms |
1792 KB |
Output is correct |
48 |
Correct |
5 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
3 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 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
13 ms |
5760 KB |
Output is correct |
14 |
Correct |
37 ms |
13972 KB |
Output is correct |
15 |
Correct |
9 ms |
4608 KB |
Output is correct |
16 |
Correct |
55 ms |
19232 KB |
Output is correct |
17 |
Correct |
49 ms |
17784 KB |
Output is correct |
18 |
Correct |
46 ms |
16888 KB |
Output is correct |
19 |
Correct |
32 ms |
12564 KB |
Output is correct |
20 |
Correct |
58 ms |
19320 KB |
Output is correct |
21 |
Correct |
59 ms |
19772 KB |
Output is correct |
22 |
Correct |
31 ms |
12152 KB |
Output is correct |
23 |
Correct |
41 ms |
14840 KB |
Output is correct |
24 |
Correct |
98 ms |
19796 KB |
Output is correct |
25 |
Correct |
77 ms |
24184 KB |
Output is correct |
26 |
Correct |
77 ms |
24184 KB |
Output is correct |
27 |
Correct |
77 ms |
24312 KB |
Output is correct |
28 |
Correct |
76 ms |
24184 KB |
Output is correct |
29 |
Correct |
75 ms |
24184 KB |
Output is correct |
30 |
Correct |
77 ms |
24160 KB |
Output is correct |
31 |
Correct |
75 ms |
24184 KB |
Output is correct |
32 |
Correct |
74 ms |
24184 KB |
Output is correct |
33 |
Correct |
78 ms |
24056 KB |
Output is correct |
34 |
Correct |
77 ms |
24148 KB |
Output is correct |
35 |
Correct |
77 ms |
24184 KB |
Output is correct |
36 |
Correct |
78 ms |
24052 KB |
Output is correct |
37 |
Correct |
73 ms |
24076 KB |
Output is correct |
38 |
Correct |
2 ms |
512 KB |
Output is correct |
39 |
Correct |
2 ms |
512 KB |
Output is correct |
40 |
Correct |
2 ms |
512 KB |
Output is correct |
41 |
Correct |
2 ms |
512 KB |
Output is correct |
42 |
Correct |
2 ms |
512 KB |
Output is correct |
43 |
Correct |
2 ms |
512 KB |
Output is correct |
44 |
Correct |
2 ms |
512 KB |
Output is correct |
45 |
Correct |
2 ms |
512 KB |
Output is correct |
46 |
Correct |
2 ms |
512 KB |
Output is correct |
47 |
Correct |
2 ms |
512 KB |
Output is correct |
48 |
Correct |
3 ms |
512 KB |
Output is correct |
49 |
Correct |
2 ms |
512 KB |
Output is correct |
50 |
Correct |
2 ms |
512 KB |
Output is correct |
51 |
Correct |
2 ms |
512 KB |
Output is correct |
52 |
Correct |
2 ms |
512 KB |
Output is correct |
53 |
Correct |
2 ms |
512 KB |
Output is correct |
54 |
Correct |
2 ms |
512 KB |
Output is correct |
55 |
Correct |
2 ms |
512 KB |
Output is correct |
56 |
Correct |
2 ms |
512 KB |
Output is correct |
57 |
Correct |
2 ms |
512 KB |
Output is correct |
58 |
Correct |
2 ms |
512 KB |
Output is correct |
59 |
Correct |
2 ms |
512 KB |
Output is correct |
60 |
Correct |
2 ms |
512 KB |
Output is correct |
61 |
Correct |
2 ms |
512 KB |
Output is correct |
62 |
Correct |
2 ms |
768 KB |
Output is correct |
63 |
Correct |
3 ms |
1024 KB |
Output is correct |
64 |
Correct |
4 ms |
512 KB |
Output is correct |
65 |
Correct |
4 ms |
1920 KB |
Output is correct |
66 |
Correct |
3 ms |
1664 KB |
Output is correct |
67 |
Correct |
4 ms |
1792 KB |
Output is correct |
68 |
Correct |
4 ms |
1920 KB |
Output is correct |
69 |
Correct |
4 ms |
1664 KB |
Output is correct |
70 |
Correct |
4 ms |
1792 KB |
Output is correct |
71 |
Correct |
4 ms |
1792 KB |
Output is correct |
72 |
Correct |
4 ms |
1792 KB |
Output is correct |
73 |
Correct |
5 ms |
1920 KB |
Output is correct |
74 |
Correct |
43 ms |
14172 KB |
Output is correct |
75 |
Correct |
12 ms |
4608 KB |
Output is correct |
76 |
Correct |
20 ms |
7652 KB |
Output is correct |
77 |
Incorrect |
73 ms |
22520 KB |
Output isn't correct |
78 |
Halted |
0 ms |
0 KB |
- |