| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117740 |
2019-06-17T07:19:12 Z |
임유진(#2881) |
Ljetopica (COI19_ljetopica) |
C++14 |
|
2 ms |
384 KB |
#include<stdio.h>
#include<stdlib.h>
#define MAXN 1005
const int MOD=1e9 + 7;
char ans[MAXN];
char A[MAXN], B[MAXN];
int two[MAXN];
long long dp[MAXN][MAXN][2][2];
bool cA[MAXN], cB[MAXN];
void add(long long* a, long long b) {
*a = (*a + b) % MOD;
}
int main() {
int N, K;
long long res;
freopen("input.txt", "r", stdin);
scanf("%d%d", &N, &K);
scanf("%s\n%s\n%s", ans, A, B);
if (A[N - 1] == 0) {
A[0] = '1';
for (int i = 1; i < N; i++) A[i] = '0';
}
if (B[N] != 0) for (int i = 0; i < N; i++) B[i] = '1';
//printf("%s*%s*%s", A, B, ans);
for (int i = 0; i < N - 1; i++) {
cA[i] = ((ans[i] == 'L' && A[i+1] == '0') || (ans[i] == 'R' && A[i+1] == '1'));
cB[i] = ((ans[i] == 'L' && B[i+1] == '0') || (ans[i] == 'R' && B[i+1] == '1'));
//printf("[%d %d]\n", cA[i]?1:0, cB[i]?1:0);
}
two[0] = 1;
for (int i = 1; i < N; i++) two[i] = two[i - 1] * 2 % MOD;
dp[N - 1][0][0][0] = dp[N-1][0][1][0]=1ll;
//printf("%lld\n", dp[2][0][1][0]);
//for (int i = 0; i < N; i++)
//for (int j = 0; j <= K; j++) printf("i=%d, j=%d: (%lld %lld), (%lld %lld)\n", i, j, dp[i][j][0][0], dp[i][j][0][1], dp[i][j][1][0], dp[i][j][1][1]);
for (int i = N - 2; i >= 0; i--) for(int j=0; j<=K; j++){
dp[i][j][0][0] = dp[i + 1][j][0][0];
dp[i][j][1][0] = dp[i + 1][j][1][0];
if (j > 0) {
add(&dp[i][j][0][0], dp[i + 1][j - 1][1][0]);
add(&dp[i][j][1][0], dp[i + 1][j - 1][0][0]);
}
dp[i][j][0][1] = dp[i + 1][j][0][1];
dp[i][j][1][1] = dp[i + 1][j][1][1];
if (ans[i] == 'L') add(&dp[i][j][1][1], two[N - i - 2] * dp[i + 1][j][1][0]);
else add(&dp[i][j][0][1], two[N - i - 2] * dp[i + 1][j][0][0]);
if (j > 0) {
add(&dp[i][j][0][1], dp[i + 1][j - 1][1][1]);
add(&dp[i][j][1][1], dp[i + 1][j - 1][0][1]);
if (ans[i] == 'L') add(&dp[i][j][0][1], two[N - i - 2] * dp[i + 1][j - 1][1][0]);
else add(&dp[i][j][1][1], two[N - i - 2] * dp[i + 1][j - 1][0][0]);
}
}
//for (int i = 0; i < N; i++)
//for (int j = 0; j <= K; j++) printf("i=%d, j=%d: (%lld %lld), (%lld %lld)\n", i, j, dp[i][j][0][0], dp[i][j][0][1], dp[i][j][1][0], dp[i][j][1][1]);
res = (dp[0][K][0][1] + dp[0][K][1][1] + two[N - 1] * (dp[0][K][0][0] + dp[0][K][1][0])) % MOD;
//printf("%lld\n", res);
long long sA=two[N-1], sB=two[N-1];
int KA = K, KB=K;
for (int i = 0; i < N - 1; i++) {
if (A[i + 1] == '1') {
//printf("@");
if (i>0&&cA[i - 1] == cA[i]) KA--;
//printf("(%d %lld)", KA, sA);
if (KA >= 0) res = (res - dp[i + 1][KA][cA[i] ? 1 : 0][1] - sA * dp[i + 1][KA][cA[i] ? 1 : 0][0]) % MOD;
if (KA > 0) res = (res - dp[i + 1][KA-1][cA[i] ? 1 : 0][1] - sA * dp[i + 1][KA-1][cA[i] ? 1 : 0][0]) % MOD;
if (i>0&&cA[i - 1] == cA[i]) KA++;
//printf("%lld", res);
add(&sA, two[N - i - 1]);
}
if (B[i + 1] == '0') {
//printf("$");
if (i>0&&cB[i - 1] == cB[i]) KB--;
//printf("(%d %lld)\n", KB, sB);
if (KB >= 0) res = (res - dp[i + 1][KB][cB[i] ? 1 : 0][1] - (sB+two[N-i-2]) * dp[i + 1][KB][cB[i] ? 1 : 0][0]) % MOD;
if(KB>0) res = (res - dp[i + 1][KB-1][cB[i] ? 1 : 0][1] - (sB+two[N-i-2]) * dp[i + 1][KB-1][cB[i] ? 1 : 0][0]) % MOD;
if (i>0&&cB[i - 1] == cB[i]) KB++;
//printf("%lld", res);
}
else add(&sB, two[N - i - 2]);
if (i > 0) {
if (cA[i - 1] != cA[i]) KA--;
if (cB[i - 1] != cB[i]) KB--;
}
res = (res + MOD) % MOD;
}
printf("%lld", res);
return 0;
}
Compilation message
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &K);
~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s\n%s\n%s", ans, A, B);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
