Submission #118051

#TimeUsernameProblemLanguageResultExecution timeMemory
118051sebinkimSolitaire (JOI16_solitaire)C++14
80 / 100
78 ms24312 KiB
#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) * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) % mod)) % 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 % mod * X3[l1] * 2 % mod + mod) % mod; dp[i][j + 1] = (dp[i][j + 1] + x * j % mod * 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)) % 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...