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

• 問題: No.3753 Certainly a Cretan
• ユーザー: marc2825
• 提出日時: 2026-08-19 00:49:20
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,902 bytes
• コンパイル時間: 606 ms
• コンパイル使用メモリ: 106,364 KB
• 実行使用メモリ: 60,544 KB
• 最終ジャッジ日時: 2026-10-02 20:56:50
• 合計ジャッジ時間: 4,823 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

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

ソースコード

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

using namespace std;

const int MOD = 998244353;

long long fact[2000005], invFact[2000005];

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = res * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= 2000000; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invFact[2000000] = power(fact[2000000], MOD - 2);
    for (int i = 1999999; i >= 1; --i) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

long long get_B(int n, int y) {
    if (y < 0) return 0;
    long long res = (nCr(2 * n, n + y) - nCr(2 * n, n + y + 2) + MOD) % MOD;
    return res;
}

long long get_A(int len) {
    return get_B(len - 1, 0);
}

long long invA(int len) {
    return power(get_A(len), MOD - 2);
}

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute();
    
    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    
    string S_str;
    cin >> S_str;
    
    vector<char> S(N + 1);
    for (int i = 1; i <= N; ++i) {
        S[i] = S_str[i - 1];
    }
    
    int m = (N + 1) / 2;
    vector<char> C(m + 1);
    for (int k = 1; k <= m; ++k) {
        C[k] = S[2 * k - 1];
    }
    
    // Nが偶数の場合、(2k-1, 2k) の不一致数を管理
    int error_count = 0;
    if (N % 2 == 0) {
        for (int k = 1; k <= N / 2; ++k) {
            if (S[2 * k - 1] != S[2 * k]) error_count++;
        }
    }
    
    // ブロック境界と経路数の積を管理
    long long Total_prod_A = 1;
    set<int> borders;
    borders.insert(0);
    borders.insert(m);
    
    int prev_pos = 0;
    for (int k = 1; k < m; ++k) {
        if (C[k] != C[k + 1]) {
            borders.insert(k);
            Total_prod_A = Total_prod_A * get_A(k - prev_pos) % MOD;
            prev_pos = k;
        }
    }
    Total_prod_A = Total_prod_A * get_A(m - prev_pos) % MOD;
    
    auto add_border = [&](int pos) {
        auto it = borders.insert(pos).first;
        int L = *prev(it);
        int R = *next(it);
        
        Total_prod_A = Total_prod_A * invA(R - L) % MOD;
        Total_prod_A = Total_prod_A * get_A(pos - L) % MOD;
        Total_prod_A = Total_prod_A * get_A(R - pos) % MOD;
    };
    
    auto remove_border = [&](int pos) {
        auto it = borders.find(pos);
        int L = *prev(it);
        int R = *next(it);
        
        Total_prod_A = Total_prod_A * invA(pos - L) % MOD;
        Total_prod_A = Total_prod_A * invA(R - pos) % MOD;
        Total_prod_A = Total_prod_A * get_A(R - L) % MOD;
        
        borders.erase(it);
    };
    
    auto toggle = [&](int pos) {
        if (borders.count(pos)) remove_border(pos);
        else add_border(pos);
    };
    
    // クエリの処理
    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            int i;
            cin >> i;
            if (N % 2 == 0) {
                int k = (i + 1) / 2;
                if (S[2 * k - 1] != S[2 * k]) error_count--;
                S[i] = (S[i] == 'Y' ? 'N' : 'Y');
                if (S[2 * k - 1] != S[2 * k]) error_count++;
            } else {
                S[i] = (S[i] == 'Y' ? 'N' : 'Y');
            }
            
            if (i % 2 != 0) {
                int k = (i + 1) / 2;
                C[k] = S[i];
                if (k > 1) toggle(k - 1);
                if (k < m) toggle(k);
            }
        } else {
            int K;
            cin >> K;
            
            if (error_count > 0) {
                cout << 0 << "\n";
            } else {
                auto it = borders.end();
                --it; --it;
                int last_L = m - *it;
                long long prod_A = Total_prod_A * invA(last_L) % MOD;
                char last_C = C[m];
                int n_val = last_L - 1;
                
                long long ans = 0;
                if (N % 2 == 0) {
                    if (last_C == 'Y') {
                        ans = (get_B(n_val, m - K) + get_B(n_val, m - K - 1)) % MOD;
                    } else {
                        ans = (get_B(n_val, K - m - 1) + get_B(n_val, K - m)) % MOD;
                    }
                } else {
                    if (last_C == 'Y') {
                        ans = get_B(n_val, N - K - m);
                    } else {
                        ans = get_B(n_val, K + m - 1 - N);
                    }
                }
                ans = ans * prod_A % MOD;
                cout << ans << "\n";
            }
        }
    }
    return 0;
}