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

• 問題: No.3753 Certainly a Cretan
• ユーザー: marc2825
• 提出日時: 2026-08-19 00:48:19
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,988 bytes
• コンパイル時間: 1,258 ms
• コンパイル使用メモリ: 226,488 KB
• 実行使用メモリ: 9,912 KB
• 最終ジャッジ日時: 2026-10-02 20:56:52
• 合計ジャッジ時間: 8,729 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 27 TLE * 2 -- * 17

ソースコード

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

using ll = long long;

const int MOD = 998244353;

ll modpow(ll a, ll n) {
    ll r = 1;
    while (n) {
        if (n & 1) r = r * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return r;
}

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

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

    string S;
    cin >> S;

    vector<ll> fact(N + 1), invfact(N + 1);

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

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

    auto C = [&](int n, int k) -> ll {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
    };

    auto cat = [&](int r) -> ll {
        return fact[2 * r] * invfact[r] % MOD * invfact[r + 1] % MOD;
    };

    vector<int> cp = {0};

    for (int x = 1; x < N; x *= 2) {
        cp.push_back(x);
        if (x > N / 2) break;
    }

    if (cp.back() != N) {
        cp.push_back(N);
    }

    int M = cp.size();

    vector<vector<int>> saved(M);

    auto build_prefix = [&](int n) {
        vector<int> dp(n + 1);

        if (n == 0) {
            dp[0] = 1;
            return dp;
        }

        int bad = 0;
        int B = 0;
        ll P = 1;
        int last = 0;

        for (int i = 1; i < n; ++i) {
            if (S[i - 1] == S[i]) continue;

            if (i & 1) {
                ++bad;
            } else {
                P = P * cat((i - last) / 2) % MOD;
                last = i;
                B = i;
            }
        }

        if (bad > 0) {
            return dp;
        }

        int L = n - B;

        for (int K = 0; K <= n; ++K) {
            int q = K - B / 2;

            if (S[n - 1] == 'Y') {
                if (0 <= q && q <= L / 2) {
                    ll f = (C(L, q) - C(L, q - 1) + MOD) % MOD;
                    dp[K] = P * f % MOD;
                }
            } else {
                if ((L + 1) / 2 <= q && q <= L) {
                    ll f = (C(L, q) - C(L, q + 1) + MOD) % MOD;
                    dp[K] = P * f % MOD;
                }
            }
        }

        return dp;
    };

    for (int j = 0; j < M; ++j) {
        saved[j] = build_prefix(cp[j]);
    }

    auto transition = [&](const vector<int>& dp, int i) {
        vector<int> ndp(i + 2);

        int people = i + 1;

        for (int k = 0; k <= i; ++k) {
            if (dp[k] == 0) continue;

            {
                int liar = k;
                int honest = people - liar;

                bool answer_yes = honest * 2 > people;

                if (answer_yes == (S[i] == 'Y')) {
                    ndp[k] += dp[k];
                    if (ndp[k] >= MOD) ndp[k] -= MOD;
                }
            }

            {
                int liar = k + 1;

                bool correct_yes = liar * 2 > people;
                bool answer_yes = !correct_yes;

                if (answer_yes == (S[i] == 'Y')) {
                    ndp[k + 1] += dp[k];
                    if (ndp[k + 1] >= MOD) ndp[k + 1] -= MOD;
                }
            }
        }

        return ndp;
    };

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

        if (t == 1) {
            int p = x - 1;

            S[p] = (S[p] == 'Y' ? 'N' : 'Y');

            int j = upper_bound(cp.begin(), cp.end(), p) - cp.begin() - 1;

            int pos = cp[j];
            vector<int> cur = saved[j];

            for (int i = pos; i < N; ++i) {
                cur = transition(cur, i);

                if (j + 1 < M && i + 1 == cp[j + 1]) {
                    ++j;

                    if (cur == saved[j]) {
                        break;
                    }

                    saved[j] = cur;
                }
            }
        } else {
            int K = x;
            cout << saved.back()[K] << '\n';
        }
    }
}