#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +1005
#define MaxS N * N
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
ll f[N][N][2][2] {0};
int lss, len, n, i, inv, z, k;
string l, r, s;
ll sm(ll x, ll y) {return (x + y) % M;}
ll mult(ll x, ll y) {return (x * y) % M;}
ll bp(ll x, ll y)
{
if (y == 0) return 1ll;
if (y % 2) return mult(bp(x, y - 1), x);
ll a = bp(x, y / 2);
return mult(a, a);
}
string dec(string x)
{
int i = n - 1;
while (i >= 0 && x[i] == '0') i--, x[i] = '1';
x[i] = '0';
return x;
}
ll calc(string x)
{
memset(f, 0, sizeof(f));
for (len = 1; len <= n; len++)
for (z = 0; z <= k; z++)
for (lss = 0; lss < 2; lss++)
for (inv = 0; inv < 2; inv++) f[len][z][lss][inv] = 0;
f[1][0][0][0] = f[1][0][0][1] = bp(2, n - 1);
for (len = 1; len < n; len++)
for (z = 0; z <= k; z++)
for (lss = 0; lss < 2; lss++)
for (inv = 0; inv < 2; inv++)
{
if (f[len][z][lss][inv] == 0) continue;
if (!inv)
{
if (s[len - 1] == 'L')
{
if (x[len] == '0')
{
if (lss == 0)
{
f[len + 1][z][lss][inv] = sm(f[len][z][lss][inv], f[len + 1][z][lss][inv]);
}
else
{
f[len + 1][z][lss][inv] = sm(f[len][z][lss][inv], f[len + 1][z][lss][inv]);
f[len + 1][z + 1][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z + 1][lss][inv]);
}
}
else
{
if (lss == 0)
{
f[len + 1][z][1][inv] = sm(f[len][z][lss][inv], f[len + 1][z][1][inv]);
f[len + 1][z + 1][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z + 1][lss][inv]);
}
else
{
f[len + 1][z][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z][lss][inv]);
f[len + 1][z + 1][1][inv] = sm(f[len + 1][z + 1][1][inv], f[len][z][lss][inv]);
}
}
}
else
{
if (x[len] == '1')
{
if (lss == 0)
{
f[len + 1][z][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z][lss][inv]);
f[len + 1][z + 1][1][inv] = sm(f[len][z][lss][inv], f[len + 1][z + 1][1][inv]);
}
else
{
f[len + 1][z][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z][lss][inv]);
f[len + 1][z + 1][lss][inv] = sm(f[len][z][lss][inv], f[len + 1][z + 1][lss][inv]);
}
}
else
{
if (lss == 0)
{
f[len + 1][z + 1][lss][inv] = sm(f[len][z][lss][inv], sm(f[len + 1][z + 1][lss][inv], bp(2, n - len - 1)));
}
else
{
f[len + 1][z + 1][lss][inv] = sm(f[len + 1][z + 1][lss][inv], f[len][z][lss][inv]);
f[len + 1][z][lss][inv] = sm(f[len + 1][z][lss][inv], sm(bp(2, n - len - 1), f[len][z][lss][inv]));
}
}
}
}
else
{
if (s[len - 1] == 'R')
{
if (x[len] == '0')
{
if (lss == 0)
{
f[len + 1][z][lss][inv] = sm(f[len][z][lss][inv], f[len + 1][z][lss][inv]);
}
else
{
f[len + 1][z][lss][inv] = sm(f[len][z][lss][inv], f[len + 1][z][lss][inv]);
f[len + 1][z + 1][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z + 1][lss][inv]);
}
}
else
{
if (lss == 0)
{
f[len + 1][z][1][inv] = sm(f[len][z][lss][inv], f[len + 1][z][1][inv]);
f[len + 1][z + 1][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z + 1][lss][inv]);
}
else
{
f[len + 1][z][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z][lss][inv]);
f[len + 1][z + 1][1][inv] = sm(f[len + 1][z + 1][1][inv], f[len][z][lss][inv]);
}
}
}
else
{
if (x[len] == '1')
{
if (lss == 0)
{
f[len + 1][z][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z][lss][inv]);
f[len + 1][z + 1][1][inv] = sm(f[len][z][lss][inv], f[len + 1][z + 1][1][inv]);
}
else
{
f[len + 1][z][lss][inv] = sm(sm(f[len][z][lss][inv], bp(2, n - len - 1)), f[len + 1][z][lss][inv]);
f[len + 1][z + 1][lss][inv] = sm(f[len][z][lss][inv], f[len + 1][z + 1][lss][inv]);
}
}
else
{
if (lss == 0)
{
f[len + 1][z + 1][lss][inv] = sm(f[len][z][lss][inv], sm(f[len + 1][z + 1][lss][inv], bp(2, n - len - 1)));
}
else
{
f[len + 1][z + 1][lss][inv] = sm(f[len + 1][z + 1][lss][inv], f[len][z][lss][inv]);
f[len + 1][z][lss][inv] = sm(f[len + 1][z][lss][inv], sm(bp(2, n - len - 1), f[len][z][lss][inv]));
}
}
}
}
}
ll ans = 0;
for (lss = 0; lss < 2; lss++)
for (inv = 0; inv < 2; inv++)
if (f[n][k][lss][inv] != 0) ans = sm(ans, f[n][k][lss][inv]);
return ans;
}
int main()
{
srand(time(0));
ios_base::sync_with_stdio(0);
iostream::sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// in("input.txt");
// out("output.txt");
cin >> n >> k;
cin >> s;
cin >> l;
cin >> r;
cout << calc(dec(l)) << el;
cout << (calc(r) - calc(dec(l)) + M) % M;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
32000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
32000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
32120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
32000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
