Submission #682043

#	Time	Username	Problem	Language	Result	Execution time	Memory
682043		Cyanmond	Ljetopica (COI19_ljetopica)	C++17	100 / 100	108 ms	15872 KiB

ljetopica

#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(inv_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() + 1, 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;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61