結果

問題 No.3753 Certainly a Cretan
コンテスト
ユーザー marc2825
提出日時 2026-08-19 00:54:15
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,265 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,029 ms
コンパイル使用メモリ 214,528 KB
実行使用メモリ 9,912 KB
最終ジャッジ日時 2026-10-02 20:57:17
合計ジャッジ時間 11,444 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

const int MOD = 998244353;

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

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

    string S;
    cin >> S;

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

        if (t == 1) {
            --x;
            S[x] = (S[x] == 'Y' ? 'N' : 'Y');
            continue;
        }

        int K = x;

        vector<int> dp(K + 1);
        dp[0] = 1;

        for (int i = 0; i < N; ++i) {
            vector<int> ndp(K + 1);

            int n = i + 1;

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

                int honest = n - k;

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

                if (k < K) {
                    int liar = k + 1;

                    bool ansY = !(liar * 2 > n);

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

            dp.swap(ndp);
        }

        cout << dp[K] << '\n';
    }
}
0