#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
const long long mod = 1000000007;
int n, k;
string path, a, b;
vector<int> pow2(2000);
int dp[1005][1005][2][2], cnt[1005][1005][2][2];
void Add(int depth, int steps, int ok, int atBound, int depth2, int steps2, int ok2, int atBound2, char dir)
{
if (max(depth, depth2) > n || max(steps, steps2) > k)
return;
if (depth == 2 && steps == 0 && ok == 0 && atBound == 1)
cerr << "";
dp[depth][steps][ok][atBound] += 2 * dp[depth2][steps2][ok2][atBound2];
if (dir == 'R')
dp[depth][steps][ok][atBound] += cnt[depth2][steps2][ok2][atBound2];
cnt[depth][steps][ok][atBound] += cnt[depth2][steps2][ok2][atBound2];
}
int Solve(string bound)
{
for (int depth = 1; depth <= n; ++depth)
for (int steps = 0; steps <= k; ++steps)
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= 1; ++j)
cnt[depth][steps][i][j] = dp[depth][steps][i][j] = 0;
dp[1][0][0][1] = dp[1][0][1][1] = 1;
cnt[1][0][0][1] = cnt[1][0][1][1] = 1;
for (int depth = 1; depth < n; ++depth)
for (int steps = 0; steps <= k; ++steps)
for (int ok = 0; ok <= 1; ++ok)
{
// += dp[][][][0]
if (depth == 2)
cerr << "";
if (path[depth - 1] == (ok ? 'L' : 'R'))
Add(depth + 1, steps, ok, 0, depth, steps, ok, 0, 'L');
else
Add(depth + 1, steps, ok, 0, depth, steps, ok, 0, 'R');
if (path[depth - 1] == (!ok ? 'L' : 'R'))
Add(depth + 1, steps + 1, !ok, 0, depth, steps, ok, 0, 'L');
else
Add(depth + 1, steps + 1, !ok, 0, depth, steps, ok, 0, 'R');
// += dp[][][][1]
if (ok)
{
if (path[depth - 1] == 'L')
Add(depth + 1, steps, ok, bound[depth - 1] == 'R' ? 0 : 1, depth, steps, ok, 1, 'L');
else if (bound[depth - 1] == 'R')
Add(depth + 1, steps, ok, 1, depth, steps, ok, 1, 'R');
}
else
{
if (path[depth - 1] == 'R')
Add(depth + 1, steps, ok, bound[depth - 1] == 'R' ? 0 : 1, depth, steps, ok, 1, 'L');
else if (bound[depth - 1] == 'R')
Add(depth + 1, steps, ok, 1, depth, steps, ok, 1, 'R');
}
if (!ok)
{
if (path[depth - 1] == 'L')
Add(depth + 1, steps + 1, !ok, bound[depth - 1] == 'R' ? 0 : 1, depth, steps, ok, 1, 'L');
else if (bound[depth - 1] == 'R')
Add(depth + 1, steps + 1, !ok, 1, depth, steps, ok, 1, 'R');
}
else
{
if (path[depth - 1] == 'R')
Add(depth + 1, steps + 1, !ok, bound[depth - 1] == 'R' ? 0 : 1, depth, steps, ok, 1, 'L');
else if (bound[depth - 1] == 'R')
Add(depth + 1, steps + 1, !ok, 1, depth, steps, ok, 1, 'R');
}
}
/*
for (int depth = 1; depth <= n; ++depth)
for (int steps = 0; steps <= k; ++steps)
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= 1; ++j)
{
cout << "dp[" << depth << "][" << steps << "][" << i << "][" << j << "] = " << dp[depth][steps][i][j] << '\t';
cout << "cnt[" << depth << "][" << steps << "][" << i << "][" << j << "] = " << cnt[depth][steps][i][j] << endl;
}
*/
int ans = 0;
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= 1; ++j)
ans += dp[n][k][i][j];
return ans;
}
int main()
{
pow2[0] = 1;
for (int i = 1; i < pow2.size(); ++i)
pow2[i] = (pow2[i - 1] + pow2[i - 1]) % mod;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k;
cin >> path;
cin >> a >> b;
reverse(a.begin(), a.end());
for (int i = 0; i < a.length(); ++i)
if (a[i] == '0')
a[i] = '1';
else
{
a[i] = '0';
if (i + 1 == a.length())
a.pop_back();
break;
}
reverse(b.begin(), b.end());
a.pop_back();
b.pop_back();
for (int i = 0; i < a.length(); ++i)
a[i] = (a[i] == '0') ? 'L' : 'R';
for (int i = 0; i < b.length(); ++i)
b[i] = (b[i] == '0') ? 'L' : 'R';
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
cout << Solve(b) - Solve(a) << endl;
char I;
cin >> I;
}
Compilation message
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < pow2.size(); ++i)
~~^~~~~~~~~~~~~
ljetopica.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.length(); ++i)
~~^~~~~~~~~~~~
ljetopica.cpp:113:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + 1 == a.length())
~~~~~~^~~~~~~~~~~~~
ljetopica.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.length(); ++i)
~~^~~~~~~~~~~~
ljetopica.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < b.length(); ++i)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
26360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
