#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MOD = 1000000007;
int bin_to_int(const string &bin) {
int value = 0;
for (char c : bin) {
value = value * 2 + (c - '0');
}
return value;
}
int add_mod(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int calculate_sum(int N, int K, const string &path, int max_value) {
vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>>(K+1, vector<vector<int>>(2, vector<int>(2, 0))));
dp[0][0][0][0] = 1; // Initial state
for (int i = 0; i < N-1; ++i) {
for (int k = 0; k <= K; ++k) {
for (int smaller = 0; smaller < 2; ++smaller) {
for (int last = 0; last < 2; ++last) {
if (dp[i][k][smaller][last] == 0) continue;
for (int move = 0; move < 2; ++move) {
int new_smaller = smaller;
if (move == 1 && (max_value & (1 << (N-2-i))) == 0) {
new_smaller = 1;
}
if (move == 0 && (max_value & (1 << (N-2-i))) != 0) {
new_smaller = 1;
}
if (path[i] == 'L' && last == 0 || path[i] == 'R' && last == 1) {
dp[i+1][k][new_smaller][0] = add_mod(dp[i+1][k][new_smaller][0], dp[i][k][smaller][last]);
} else {
dp[i+1][k][new_smaller][1] = add_mod(dp[i+1][k][new_smaller][1], dp[i][k][smaller][last]);
}
if (k < K) {
if (path[i] == 'L' && last == 1 || path[i] == 'R' && last == 0) {
dp[i+1][k+1][new_smaller][0] = add_mod(dp[i+1][k+1][new_smaller][0], dp[i][k][smaller][last]);
} else {
dp[i+1][k+1][new_smaller][1] = add_mod(dp[i+1][k+1][new_smaller][1], dp[i][k][smaller][last]);
}
}
}
}
}
}
}
int sum = 0;
for (int k = 0; k <= K; ++k) {
for (int smaller = 0; smaller < 2; ++smaller) {
for (int last = 0; last < 2; ++last) {
sum = add_mod(sum, dp[N-1][k][smaller][last]);
}
}
}
return sum;
}
int main() {
int N, K;
cin >> N >> K;
string path;
cin >> path;
string binA, binB;
cin >> binA >> binB;
int A = bin_to_int(binA);
int B = bin_to_int(binB);
int sumB = calculate_sum(N, K, path, B);
int sumA_minus_1 = calculate_sum(N, K, path, A - 1);
int result = (sumB - sumA_minus_1 + MOD) % MOD;
cout << result << endl;
return 0;
}
Compilation message
ljetopica.cpp: In function 'int calculate_sum(int, int, const string&, int)':
ljetopica.cpp:42:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
42 | if (path[i] == 'L' && last == 0 || path[i] == 'R' && last == 1) {
ljetopica.cpp:48:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
48 | if (path[i] == 'L' && last == 1 || path[i] == 'R' && last == 0) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
85848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
