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

• 問題: No.3753 Certainly a Cretan
• ユーザー: marc2825
• 提出日時: 2026-08-19 01:18:50
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,734 bytes
• コンパイル時間: 431 ms
• コンパイル使用メモリ: 96,072 KB
• 実行使用メモリ: 102,968 KB
• 最終ジャッジ日時: 2026-10-02 20:58:01
• 合計ジャッジ時間: 11,242 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	WA * 2
other	AC * 1 WA * 45

ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

static const int MOD = 998244353;

// 多項式（嘘つきの人数 0, 1, 2 を追跡）
struct Poly {
    long long c[3];
    Poly() { c[0] = c[1] = c[2] = 0; }
    Poly(long long c0, long long c1, long long c2) {
        c[0] = (c0 % MOD + MOD) % MOD;
        c[1] = (c1 % MOD + MOD) % MOD;
        c[2] = (c2 % MOD + MOD) % MOD;
    }
    Poly operator+(const Poly& o) const {
        return Poly((c[0] + o.c[0]) % MOD, (c[1] + o.c[1]) % MOD, (c[2] + o.c[2]) % MOD);
    }
};

// 2x2 状態遷移行列
// 状態 0: C >= 0 側 (正の領域)
// 状態 1: C <= 0 側 (負の領域)
struct Mat {
    Poly d[2][2];
    Mat() {}
    static Mat identity() {
        Mat res;
        res.d[0][0] = Poly(1, 0, 0);
        res.d[1][1] = Poly(1, 0, 0);
        return res;
    }
};

Mat multiply(const Mat& A, const Mat& B) {
    Mat res;
    for (int i = 0; i < 2; i++) {
        for (int k = 0; k < 2; k++) {
            for (int j = 0; j < 2; j++) {
                // 多項式同士の畳み込み
                long long p0 = (A.d[i][k].c[0] * B.d[k][j].c[0]) % MOD;
                long long p1 = (A.d[i][k].c[0] * B.d[k][j].c[1] + A.d[i][k].c[1] * B.d[k][j].c[0]) % MOD;
                long long p2 = (A.d[i][k].c[0] * B.d[k][j].c[2] + A.d[i][k].c[1] * B.d[k][j].c[1] + A.d[i][k].c[2] * B.d[k][j].c[0]) % MOD;
                
                res.d[i][j].c[0] = (res.d[i][j].c[0] + p0) % MOD;
                res.d[i][j].c[1] = (res.d[i][j].c[1] + p1) % MOD;
                res.d[i][j].c[2] = (res.d[i][j].c[2] + p2) % MOD;
            }
        }
    }
    return res;
}

// 2文字 (S[2k-1], S[2k]) から 1 つの 2x2 遷移行列を作成
Mat make_block_mat(char s1, char s2) {
    Mat M;
    // T_i = +1 (正直者, 嘘つき0人), T_i = -1 (嘘つき, 嘘つき1人)
    int choices[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    
    for (auto& ch : choices) {
        int t1 = ch[0], t2 = ch[1];
        int liars = (t1 == -1) + (t2 == -1);

        for (int from = 0; from < 2; from++) {
            // from = 0 は C_prev >= 0, from = 1 は C_prev <= 0
            int c0 = (from == 0 ? 0 : 0);
            int c1 = c0 + t1;
            int c2 = c1 + t2;

            // 1ステップ目 (奇数) の検証
            bool ok1 = (s1 == 'Y' && c1 > 0) || (s1 == 'N' && c1 < 0);
            if (!ok1) continue;

            // 2ステップ目 (偶数) の検証
            bool ok2 = false;
            if (c2 > 0 && s2 == 'Y') ok2 = true;
            else if (c2 < 0 && s2 == 'N') ok2 = true;
            else if (c2 == 0) {
                if (s2 == 'N' && t2 == 1) ok2 = true;
                if (s2 == 'Y' && t2 == -1) ok2 = true;
            }
            if (!ok2) continue;

            int to = (c2 >= 0 ? 0 : 1);
            M.d[from][to].c[liars] = (M.d[from][to].c[liars] + 1) % MOD;
        }
    }
    return M;
}

// セグメント木
struct SegTree {
    int sz;
    vector<Mat> tree;

    void init(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        tree.assign(2 * sz, Mat::identity());
    }

    void update(int idx, const Mat& val) {
        idx += sz;
        tree[idx] = val;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = multiply(tree[2 * idx], tree[2 * idx + 1]);
        }
    }

    Mat get_total() const {
        return tree[1];
    }
};

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

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    string S;
    cin >> S;

    bool odd = (N % 2 != 0);
    if (odd) {
        // N が奇数の場合はダミー文字を追加して偶数長に揃える
        S += 'Y';
    }

    int blocks = (N + 1) / 2;
    SegTree seg;
    seg.init(blocks);

    auto update_block = [&](int blk) {
        char s1 = S[2 * blk];
        char s2 = S[2 * blk + 1];
        seg.update(blk, make_block_mat(s1, s2));
    };

    for (int i = 0; i < blocks; i++) {
        update_block(i);
    }

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int idx;
            cin >> idx;
            idx--; // 0-indexed
            S[idx] = (S[idx] == 'Y' ? 'N' : 'Y');
            update_block(idx / 2);
        } else {
            int K;
            cin >> K;
            Mat tot = seg.get_total();

            // 初期状態 C_0 = 0 は from = 0 または from = 1 のいずれから開始しても整合
            long long ans = 0;
            if (K >= 0 && K <= 2) {
                // 状態 0, 1 への到達経路の合計
                ans = (tot.d[0][0].c[K] + tot.d[0][1].c[K]) % MOD;
            }
            cout << ans << "\n";
        }
    }

    return 0;
}