#1191022 (C++17) No.3753 Certainly a Cretan

• 問題: No.3753 Certainly a Cretan
• ユーザー: marc2825
• 提出日時: 2026-10-02 17:11:47
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 70 ms / 2,500 ms
• コード長: 4,466 bytes
• コンパイル時間: 1,229 ms
• コンパイル使用メモリ: 226,124 KB
• 実行使用メモリ: 39,668 KB
• 最終ジャッジ日時: 2026-10-02 21:07:05
• 合計ジャッジ時間: 4,961 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 46

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 998244353;

int mod_pow(int a, int e) {
    long long result = 1;
    long long base = a;

    while (e > 0) {
        if (e & 1) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        e >>= 1;
    }

    return static_cast<int>(result);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    string s;
    cin >> s;
    s = " " + s;

    vector<int> fact(N + 1);
    vector<int> inv_fact(N + 1);

    fact[0] = 1;
    for (int i = 1; i <= N; ++i) {
        fact[i] = 1LL * fact[i - 1] * i % MOD;
    }

    inv_fact[N] = mod_pow(fact[N], MOD - 2);
    for (int i = N; i >= 1; --i) {
        inv_fact[i - 1] = 1LL * inv_fact[i] * i % MOD;
    }

    const int M = N / 2;
    vector<int> cat(M + 1);
    vector<int> inv_cat(M + 1);

    for (int i = 0; i <= M; ++i) {
        cat[i] = 1LL * fact[2 * i] * inv_fact[i] % MOD
                 * inv_fact[i + 1] % MOD;

        inv_cat[i] = 1LL * inv_fact[2 * i] * fact[i] % MOD
                     * fact[i + 1] % MOD;
    }

    auto combination = [&](int n, int k) -> int {
        if (k < 0 || k > n) {
            return 0;
        }
        return 1LL * fact[n] * inv_fact[k] % MOD
               * inv_fact[n - k] % MOD;
    };

    set<int> boundaries;
    boundaries.insert(0);

    int bad = 0;
    int last_boundary = 0;
    long long product = 1;

    for (int i = 1; i < N; ++i) {
        if (s[i] == s[i + 1]) {
            continue;
        }

        if (i & 1) {
            ++bad;
        } else {
            product = product * cat[(i - last_boundary) / 2] % MOD;
            last_boundary = i;

            // 昇順なので、末尾をヒントにして挿入する。
            boundaries.insert(boundaries.end(), i);
        }
    }
    boundaries.insert(boundaries.end(), N);

    auto weight = [&](int l, int r) -> int {
        if (r == N) {
            return 1;
        }
        return cat[(r - l) / 2];
    };

    auto inverse_weight = [&](int l, int r) -> int {
        if (r == N) {
            return 1;
        }
        return inv_cat[(r - l) / 2];
    };

    auto add_boundary = [&](int x) {
        auto it = boundaries.lower_bound(x);
        int r = *it;
        int l = *prev(it);

        product = product * inverse_weight(l, r) % MOD;
        product = product * weight(l, x) % MOD;
        product = product * weight(x, r) % MOD;

        boundaries.insert(it, x);

        if (r == N) {
            last_boundary = x;
        }
    };

    auto remove_boundary = [&](int x) {
        auto it = boundaries.find(x);
        int l = *prev(it);
        int r = *next(it);

        product = product * inverse_weight(l, x) % MOD;
        product = product * inverse_weight(x, r) % MOD;
        product = product * weight(l, r) % MOD;

        boundaries.erase(it);

        if (r == N) {
            last_boundary = l;
        }
    };

    while (Q--) {
        int type, x;
        cin >> type >> x;

        if (type == 1) {
            s[x] = (s[x] == 'Y' ? 'N' : 'Y');

            for (int b = x - 1; b <= x; ++b) {
                if (b <= 0 || b >= N) {
                    continue;
                }

                bool exists = (s[b] != s[b + 1]);

                // 一文字の反転により、境界の有無は必ず反転する。
                if (b & 1) {
                    bad += (exists ? 1 : -1);
                } else {
                    if (exists) {
                        add_boundary(b);
                    } else {
                        remove_boundary(b);
                    }
                }
            }

            continue;
        }

        int K = x;

        if (bad != 0) {
            cout << 0 << '\n';
            continue;
        }

        int balance = N - 2 * K;

        if ((s[N] == 'Y' && balance < 0) ||
            (s[N] == 'N' && balance > 0)) {
            cout << 0 << '\n';
            continue;
        }

        int len = N - last_boundary;
        int distance = abs(balance);

        if (distance > len) {
            cout << 0 << '\n';
            continue;
        }

        int down = (len - distance) / 2;
        int ways = combination(len, down)
                   - combination(len, down - 1);

        if (ways < 0) {
            ways += MOD;
        }

        cout << product * ways % MOD << '\n';
    }

    return 0;
}