#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 mod = 1000000007;
i64 add(i64 a, i64 b) {
return (a + b) % mod;
}
void tadd(i64 &a, i64 b) {
a = add(a, b);
}
i64 sub(i64 a, i64 b) {
return ((a - b) % mod + mod) % mod;
}
i64 mul(i64 a, i64 b) {
return (a * b) % mod;
}
constexpr i64 maxN = 5000;
std::array<i64, maxN> fact, inv, inv_fact, pow_2;
void init() {
fact[0] = fact[1] = inv[1] = inv_fact[0] = inv_fact[1] = 1;
pow_2[0] = 1, pow_2[1] = 2;
for (int i = 2; i < maxN; ++i) {
fact[i] = mul(fact[i - 1], i);
inv[i] = mod - mul(inv[mod % i], mod / i);
inv_fact[i] = mul(fact[i - 1], inv[i]);
pow_2[i] = mul(pow_2[i - 1], 2);
}
}
i64 combination(i64 n, i64 k) {
if (n < 0 or k < 0 or n < k) {
return 0;
}
return mul(fact[n], mul(inv_fact[n - k], inv_fact[k]));
}
void minus_1(std::string &x) {
const int n = (int)x.size();
for (int i = n - 1; i >= 0; --i) {
if (x[i] == '0') {
continue;
}
x[i] = '0';
for (int j = i + 1; j < n; ++j) {
x[j] = '1';
}
break;
}
}
int main() {
init();
int N, K;
std::cin >> N >> K;
std::string S;
std::cin >> S;
std::string A, B;
std::cin >> A >> B;
auto solve = [&](const std::string C) -> i64 {
// solve for [0, C]
// pre- calc
std::vector dp(N, std::vector(K + 1, std::array<i64, 2>{{0, 0}}));
dp[N - 1][0][S[N - 2] == 'R' ? 0 : 1] = 1;
for (int i = N - 1; i >= 2; --i) {
int c = S[i - 2] == 'R' ? 0 : 1;
for (int j = 0; j <= std::min(K, N - i - 1); ++j) {
for (int s = 0; s < 2; ++s) {
for (int nx = 0; nx < 2; ++nx) {
if (j + nx > K) {
continue;
}
// from dp[i][j][s] to dp[i - 1][j + nx][s]
// nm
const i64 ym = combination(N - i - 1, j);
// default
tadd(dp[i - 1][j + nx][s], dp[i][j][s]);
// add
if ((j + nx + c) % 2 == (s % 2)) {
tadd(dp[i - 1][j + nx][s], mul(pow_2[N - i], ym));
}
}
}
}
}
auto dfs = [&](auto &&self, const int t, int count_change) -> i64 {
if (count_change > K or (N - t - 1) < (K - count_change)) {
return 0;
}
if (t == N - 1) {
i64 ret = 0;
for (int i = 0; i < N; ++i) {
if (C[i] == '1') {
tadd(ret, pow_2[N - i - 1]);
}
}
return ret;
}
if (C[t + 1] == '0') {
// now direction
bool now_dir = (count_change % 2) xor (S[t] == 'L');
const int cost = now_dir ? 0 : 1;
return self(self, t + 1, count_change + cost);
} else {
bool now_dir = (count_change % 2) xor (S[t] == 'L');
const int cost = !now_dir ? 0 : 1;
count_change += cost;
const i64 res_right = self(self, t + 1, count_change);
count_change -= cost;
count_change += (1 - cost);
// calculate the left-side cost
const int k = K - count_change, r = N - t - 2;
if (k < 0 or k > r) {
// skip
return res_right;
}
// part of ancestors
i64 sum_acs = 0;
for (int i = 0; i <= t; ++i) {
if (C[i] == '1') {
tadd(sum_acs, pow_2[N - i - 1]);
}
}
i64 res_left = mul(sum_acs, combination(r, k));
// part of children
if (t != N - 2) {
for (int s = 0; s < 2; ++s) {
if (k - s < 0) {
continue;
}
if (k == r and s == 0) {
continue;
}
tadd(res_left, dp[t + 2][k - s][K % 2]);
}
}
return res_left + res_right;
}
};
return dfs(dfs, 0, 0);
};
auto calc_ans_ot = [&]() {
i64 answer = solve(B);
if (std::any_of(A.begin(), A.end(), [&](char x) { return x == '1'; })) {
auto ad = A;
minus_1(ad);
answer = sub(answer, solve(ad));
}
return answer;
};
i64 answer = calc_ans_ot();
for (auto &e : S) {
e = e == 'L' ? 'R' : 'L';
}
tadd(answer, calc_ans_ot());
answer = (answer % mod + mod) % mod;
std::cout << answer << std::endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
480 KB |
Output is correct |
| 4 |
Correct |
1 ms |
480 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
480 KB |
Output is correct |
| 4 |
Correct |
1 ms |
480 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
