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

• 問題: No.3753 Certainly a Cretan
• ユーザー: marc2825
• 提出日時: 2026-08-19 01:05:04
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 7,272 bytes
• コンパイル時間: 1,225 ms
• コンパイル使用メモリ: 223,716 KB
• 実行使用メモリ: 9,864 KB
• 最終ジャッジ日時: 2026-10-02 20:57:56
• 合計ジャッジ時間: 11,667 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_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;
    };

    /*
        現在の S の先頭 n 文字だけを考えたときの

        dp[k] =
        「先頭 n 人のうち嘘つきが k 人で、
          先頭 n 人の回答と整合する割り当て数」

        を O(n) で構築する。

        差分 DP の開始地点 dp_{p-1} を得るために使う。
    */
    auto build_prefix_dp = [&](int n) {
        vector<int> dp(n + 1);

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

        int bad = 0;
        int last = 0;
        int B = 0;

        ll P = 1;

        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;

        if (S[n - 1] == 'Y') {
            for (int q = 0; q <= L / 2; ++q) {
                int k = B / 2 + q;

                ll f = (
                    C(L, q)
                    - C(L, q - 1)
                    + MOD
                ) % MOD;

                dp[k] = P * f % MOD;
            }
        } else {
            for (int q = (L + 1) / 2; q <= L; ++q) {
                int k = B / 2 + q;

                ll f = (
                    C(L, q)
                    - C(L, q + 1)
                    + MOD
                ) % MOD;

                dp[k] = P * f % MOD;
            }
        }

        return dp;
    };

    // 現在の最終 DP。
    vector<int> final_dp = build_prefix_dp(N);

    // suffix に伝播させる差分 DP
    vector<int> diff(N + 1);
    vector<int> nxt(N + 1);

    /*
        v = dp_{t-1}

        人 t の回答が ch のとき、
        その DP 遷移の寄与を out に sign 倍して足す。

        sign = +1 : 新しい遷移
        sign = -1 : 古い遷移
    */
    auto add_transition = [&](const vector<int>& v,
                              int t,
                              char ch,
                              int sign,
                              vector<int>& out) {
        for (int k = 0; k < t; ++k) {
            if (v[k] == 0) continue;

            int val = v[k];

            // 人 t を正直者にする。
            {
                int honest = t - k;

                bool answer_yes = honest * 2 > t;

                if (answer_yes == (ch == 'Y')) {
                    ll x = out[k] + (ll)sign * val;
                    x %= MOD;
                    if (x < 0) x += MOD;
                    out[k] = x;
                }
            }

            // 人 t を嘘つきにする。
            {
                int liar = k + 1;

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

                if (answer_yes == (ch == 'Y')) {
                    ll x = out[k + 1] + (ll)sign * val;
                    x %= MOD;
                    if (x < 0) x += MOD;
                    out[k + 1] = x;
                }
            }
        }
    };

    /*
        差分 DP に、人 t の通常の遷移を1回適用する。

        [lo, hi] の範囲にしか差分がないものとして、
        その範囲だけを見る。
    */
    auto propagate = [&](int t, char ch, int lo, int hi) {
        int nlo = lo;
        int nhi = min(t, hi + 1);

        for (int k = nlo; k <= nhi; ++k) {
            nxt[k] = 0;
        }

        for (int k = lo; k <= hi; ++k) {
            if (diff[k] == 0) continue;

            int val = diff[k];

            // 正直者
            {
                int honest = t - k;

                bool answer_yes = honest * 2 > t;

                if (answer_yes == (ch == 'Y')) {
                    nxt[k] += val;
                    if (nxt[k] >= MOD) nxt[k] -= MOD;
                }
            }

            // 嘘つき
            {
                int liar = k + 1;

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

                if (answer_yes == (ch == 'Y')) {
                    nxt[k + 1] += val;
                    if (nxt[k + 1] >= MOD) nxt[k + 1] -= MOD;
                }
            }
        }

        while (nlo <= nhi && nxt[nlo] == 0) ++nlo;
        while (nlo <= nhi && nxt[nhi] == 0) --nhi;

        for (int k = lo; k <= hi; ++k) {
            diff[k] = 0;
        }

        if (nlo <= nhi) {
            for (int k = nlo; k <= nhi; ++k) {
                diff[k] = nxt[k];
            }
        }

        return pair<int, int>{nlo, nhi};
    };

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

        if (type == 2) {
            cout << final_dp[x] << '\n';
            continue;
        }

        int p = x;  // 1-indexed

        /*
            S_p を変えても dp_{p-1} までは変化しない。
        */
        vector<int> pref = build_prefix_dp(p - 1);

        char old_char = S[p - 1];
        char new_char = (old_char == 'Y' ? 'N' : 'Y');

        /*
            Δdp_p
              = T_new dp_{p-1}
              - T_old dp_{p-1}
        */
        for (int k = 0; k <= p; ++k) {
            diff[k] = 0;
        }

        add_transition(pref, p, new_char, +1, diff);
        add_transition(pref, p, old_char, -1, diff);

        S[p - 1] = new_char;

        int lo = 0;
        int hi = p;

        while (lo <= hi && diff[lo] == 0) ++lo;
        while (lo <= hi && diff[hi] == 0) --hi;

        /*
            Δdp_p を p+1, p+2, ... と後ろへ伝播。

            差分が 0 になったら、それより後ろには
            一切影響しないので終了できる。
        */
        for (int t = p + 1; t <= N && lo <= hi; ++t) {
            tie(lo, hi) = propagate(
                t,
                S[t - 1],
                lo,
                hi
            );
        }

        /*
            final_dp_new
              = final_dp_old + Δdp_N
        */
        if (lo <= hi) {
            for (int k = lo; k <= hi; ++k) {
                final_dp[k] += diff[k];

                if (final_dp[k] >= MOD) {
                    final_dp[k] -= MOD;
                }
            }
        }

        for (int k = max(0, lo); k <= hi; ++k) {
            diff[k] = 0;
        }
    }
}