#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
const int MOD = (int) 1e9 + 7;
const int MAXN = 1000;
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(string &str, int x) {
reverse(str.begin(), str.end());
int i = 0;
while(str[i] == 0) {
str[i] = 9;
i++;
}
str[i]--;
while(str.size() && str.back() == 0) {
str.pop_back();
}
reverse(str.begin(), str.end());
}
string str;
int n, k;
int dp[MAXN + 1][MAXN + 1][2];
int cnt[MAXN + 1][MAXN + 1][2];
inline int solve(string &s) {
if(s.size() < n) {
return 0;
}
for(int i = 1; i < n; i++) {
s[i - 1] = s[i];
}
int ans = 0;
for(int t = 0; t < 2; t++) {
for(auto &it : str) {
it ^= 1;
}
memset(dp, 0, sizeof(dp));
memset(cnt, 0, sizeof(cnt));
dp[0][0][1] = cnt[0][0][1] = 1;
for(int i = 0; i < n - 1; i++) {
for(int j = 0; j <= i; j++) {
for(int jj = 0; jj < 2; jj++) {
if((j + jj) & 1) {
str[i] ^= 1;
}
if(s[i] == 0) {
if(str[i] == 0) {
add(dp[i + 1][j + jj][0], (2LL * dp[i][j][0]) % MOD);
add(cnt[i + 1][j + jj][0], cnt[i][j][0]);
add(dp[i + 1][j + jj][1], (2LL * dp[i][j][1]) % MOD);
add(cnt[i + 1][j + jj][1], cnt[i][j][1]);
}
else {
add(dp[i + 1][j + jj][0], (2LL * dp[i][j][0] + cnt[i][j][0]) % MOD);
add(cnt[i + 1][j + jj][0], cnt[i][j][0]);
}
}
else {
if(str[i] == 0) {
add(dp[i + 1][j + jj][0], (2LL * (dp[i][j][0] + dp[i][j][1])) % MOD);
add(cnt[i + 1][j + jj][0], (cnt[i][j][0] + cnt[i][j][1]) % MOD);
}
else {
add(dp[i + 1][j + jj][0], (2LL * dp[i][j][0] + cnt[i][j][0]) % MOD);
add(cnt[i + 1][j + jj][0], cnt[i][j][0]);
add(dp[i + 1][j + jj][1], (2LL * dp[i][j][1] + cnt[i][j][1]) % MOD);
add(cnt[i + 1][j + jj][1], cnt[i][j][1]);
}
}
if((j + jj) & 1) {
str[i] ^= 1;
}
}
}
}
ans = (ans + dp[n - 1][k][0] + dp[n - 1][k][1]) % MOD;
}
return ans;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
//int ;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string l, r;
cin >> n >> k >> str >> l >> r;
for(auto &it : str) {
if(it == 'L') it = 0;
else it = 1;
}
for(auto &it : l) {
it -= '0';
}
for(auto &it : r) {
it -= '0';
}
sub(l, 1);
int ans = solve(r);
ans = (ans + MOD - solve(l)) % MOD;
cout << ans;
//cin.close();
//cout.close();
return 0;
}
Compilation message
ljetopica.cpp: In function 'int solve(std::__cxx11::string&)':
ljetopica.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(s.size() < n) {
~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
16000 KB |
Output is correct |
2 |
Correct |
52 ms |
16000 KB |
Output is correct |
3 |
Correct |
49 ms |
16000 KB |
Output is correct |
4 |
Correct |
52 ms |
16000 KB |
Output is correct |
5 |
Correct |
41 ms |
16092 KB |
Output is correct |
6 |
Correct |
40 ms |
16000 KB |
Output is correct |
7 |
Correct |
36 ms |
16000 KB |
Output is correct |
8 |
Correct |
36 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
16000 KB |
Output is correct |
2 |
Correct |
20 ms |
16108 KB |
Output is correct |
3 |
Correct |
19 ms |
16044 KB |
Output is correct |
4 |
Correct |
18 ms |
16000 KB |
Output is correct |
5 |
Correct |
17 ms |
16000 KB |
Output is correct |
6 |
Correct |
19 ms |
16000 KB |
Output is correct |
7 |
Correct |
19 ms |
16000 KB |
Output is correct |
8 |
Correct |
19 ms |
16000 KB |
Output is correct |
9 |
Correct |
20 ms |
16000 KB |
Output is correct |
10 |
Correct |
21 ms |
16000 KB |
Output is correct |
11 |
Correct |
22 ms |
15992 KB |
Output is correct |
12 |
Correct |
21 ms |
16000 KB |
Output is correct |
13 |
Correct |
23 ms |
16000 KB |
Output is correct |
14 |
Correct |
19 ms |
16000 KB |
Output is correct |
15 |
Correct |
24 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
16092 KB |
Output is correct |
2 |
Correct |
50 ms |
16000 KB |
Output is correct |
3 |
Correct |
48 ms |
16000 KB |
Output is correct |
4 |
Correct |
53 ms |
16000 KB |
Output is correct |
5 |
Incorrect |
51 ms |
16000 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
16000 KB |
Output is correct |
2 |
Correct |
52 ms |
16000 KB |
Output is correct |
3 |
Correct |
49 ms |
16000 KB |
Output is correct |
4 |
Correct |
52 ms |
16000 KB |
Output is correct |
5 |
Correct |
41 ms |
16092 KB |
Output is correct |
6 |
Correct |
40 ms |
16000 KB |
Output is correct |
7 |
Correct |
36 ms |
16000 KB |
Output is correct |
8 |
Correct |
36 ms |
16000 KB |
Output is correct |
9 |
Correct |
24 ms |
16000 KB |
Output is correct |
10 |
Correct |
20 ms |
16108 KB |
Output is correct |
11 |
Correct |
19 ms |
16044 KB |
Output is correct |
12 |
Correct |
18 ms |
16000 KB |
Output is correct |
13 |
Correct |
17 ms |
16000 KB |
Output is correct |
14 |
Correct |
19 ms |
16000 KB |
Output is correct |
15 |
Correct |
19 ms |
16000 KB |
Output is correct |
16 |
Correct |
19 ms |
16000 KB |
Output is correct |
17 |
Correct |
20 ms |
16000 KB |
Output is correct |
18 |
Correct |
21 ms |
16000 KB |
Output is correct |
19 |
Correct |
22 ms |
15992 KB |
Output is correct |
20 |
Correct |
21 ms |
16000 KB |
Output is correct |
21 |
Correct |
23 ms |
16000 KB |
Output is correct |
22 |
Correct |
19 ms |
16000 KB |
Output is correct |
23 |
Correct |
24 ms |
16000 KB |
Output is correct |
24 |
Correct |
58 ms |
16092 KB |
Output is correct |
25 |
Correct |
50 ms |
16000 KB |
Output is correct |
26 |
Correct |
48 ms |
16000 KB |
Output is correct |
27 |
Correct |
53 ms |
16000 KB |
Output is correct |
28 |
Incorrect |
51 ms |
16000 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |