#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int N;
long long C[1009][1009][2], D[1009][1009][2], bi[1009];
char S[1009], A[1009], B[1009];
void go(int idx, int left, bool ok) {
long long &CC = C[idx][left][ok], &DD = D[idx][left][ok];
if(idx == N) {
if(left == 0) CC = DD = 1;
else CC = DD = 0;
return;
}
if(DD != -1) return;
char X = S[idx];
if(!ok) {
if(X == 'L') X = 'R';
else X = 'L';
}
go(idx+1, left, ok);
if(left) go(idx+1, left-1, !ok);
CC = C[idx+1][left][ok];
if(left) CC += C[idx+1][left-1][!ok];
CC %= MOD;
if(X == 'L') {
DD = D[idx+1][left][ok] + C[idx+1][left][ok] * bi[N - idx - 1] % MOD;
DD %= MOD;
if(left) DD += D[idx+1][left-1][!ok] + C[idx+1][left-1][!ok] * bi[N - idx] % MOD, DD %= MOD;
}
else {
DD = D[idx+1][left][ok] + C[idx+1][left][ok] * bi[N - idx] % MOD;
DD %= MOD;
if(left) DD += D[idx+1][left-1][!ok] + C[idx+1][left-1][!ok] * bi[N - idx - 1] % MOD, DD %= MOD;
}
}
int main() {
int K; scanf("%d%d",&N,&K);
bi[0] = 1; for(int i=1; i<=N; i++) bi[i] = bi[i-1] * 2 % MOD;
scanf(" %s %s %s", S+1, A, B);
memset(D, -1, sizeof(D));
go(1, K, 1); go(1, K, 0);
long long ans = (D[1][K][0] + D[1][K][1]) % MOD; int c1 = 0, c2 = 0;
//printf("before: %lld\n",ans);
long long x = 1;
for(int i=1; i<N; i++) {
if(A[i] == '1') {
if(S[i] == 'R') ++c1;
if(S[i] == 'L') ++c2;
x = x * 2;
if(c1 <= K) {
ans += MOD - (D[i+1][K - c1][(c1 + 1) % 2] + C[i+1][K - c1][(c1 + 1) % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
//printf("D: %lld, C: %lld, x-1: %lld, bi: %lld\n", D[i+1][K - c1][(c1 + 1) % 2], C[i+1][K - c1][(c1 + 1) % 2], x - 1, bi[N - i - 1]);
}
ans %= MOD;
if(c2 <= K) {
ans += MOD - (D[i+1][K - c2][c2 % 2] + C[i+1][K - c2][c2 % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
//printf("D: %lld\n", D[i+1][K - c2][c2 % 2]);
}
ans %= MOD;
x = x / 2;
if(S[i] == 'R') --c1;
if(S[i] == 'L') --c2;
}
if(A[i] == '1') {
x = (x<<1) | 1;
x %= MOD;
if(S[i] == 'L') ++c1;
if(S[i] == 'R') ++c2;
}
else {
x = (x<<1);
x %= MOD;
if(S[i] == 'L') ++c2;
if(S[i] == 'R') ++c1;
}
//printf("ans: %lld\n", ans);
}
//printf("middle: %lld\n", ans);
c1 = c2 = 0; x = 1;
for(int i=1; i<N; i++) {
if(B[i] == '0') {
if(S[i] == 'L') ++c1;
if(S[i] == 'R') ++c2;
x = x*2+1;
if(c1 <= K) {
ans += MOD - (D[i+1][K - c1][(c1 + 1) % 2] + C[i+1][K - c1][(c1 + 1) % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
//printf("D: %lld, C: %lld, x-1: %lld, bi: %lld\n", D[i+1][K - c1][(c1 + 1) % 2], C[i+1][K - c1][(c1 + 1) % 2], x - 1, bi[N - i - 1]);
}
ans %= MOD;
if(c2 <= K) {
ans += MOD - (D[i+1][K - c2][c2 % 2] + C[i+1][K - c2][c2 % 2] * (x + MOD - 1) % MOD * bi[N - i - 1] % MOD) % MOD;
//printf("D: %lld, C: %lld, x-1: %lld, bi: %lld\n", D[i+1][K - c2][c2 % 2], C[i+1][K - c2][c2 % 2], x - 1, bi[N - i - 1]);
}
ans %= MOD;
x = x/2;
if(S[i] == 'L') --c1, x = x >> 1;
if(S[i] == 'R') --c2, x = x-1 >> 1;
}
if(B[i] == '0') {
x = (x<<1);
x %= MOD;
if(S[i] == 'R') ++c1;
if(S[i] == 'L') ++c2;
}
else {
x = (x<<1) | 1;
x %= MOD;
if(S[i] == 'R') ++c2;
if(S[i] == 'L') ++c1;
}
}
printf("%lld", ans);
return 0;
}
Compilation message
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:112:34: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
if(S[i] == 'R') --c2, x = x-1 >> 1;
~^~
ljetopica.cpp:46:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int K; scanf("%d%d",&N,&K);
~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s %s %s", S+1, A, B);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
20352 KB |
Output is correct |
| 2 |
Correct |
18 ms |
20224 KB |
Output is correct |
| 3 |
Correct |
17 ms |
19968 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
18 ms |
19584 KB |
Output is correct |
| 6 |
Correct |
17 ms |
19328 KB |
Output is correct |
| 7 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 8 |
Correct |
16 ms |
18944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
16384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
26744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
20352 KB |
Output is correct |
| 2 |
Correct |
18 ms |
20224 KB |
Output is correct |
| 3 |
Correct |
17 ms |
19968 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
18 ms |
19584 KB |
Output is correct |
| 6 |
Correct |
17 ms |
19328 KB |
Output is correct |
| 7 |
Correct |
17 ms |
19200 KB |
Output is correct |
| 8 |
Correct |
16 ms |
18944 KB |
Output is correct |
| 9 |
Incorrect |
14 ms |
16384 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
