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

• 問題: No.3753 Certainly a Cretan
• ユーザー: marc2825
• 提出日時: 2026-08-19 00:48:41
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 154 ms / 2,500 ms
• コード長: 2,869 bytes
• コンパイル時間: 1,288 ms
• コンパイル使用メモリ: 228,108 KB
• 実行使用メモリ: 44,700 KB
• 最終ジャッジ日時: 2026-10-02 20:56:52
• 合計ジャッジ時間: 4,726 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 46

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const ll MOD = 998244353;

int N, Q;
static char S[1000006];
vector<ll> fac, ifac;
set<int> bnd;      // run 境界（番兵 0, N を含む）
ll Prod = 1;       // 偶数長 run すべての Catalan(len/2) の積
int oddCnt = 0;    // 奇数長 run の個数

ll pw(ll b, ll e){ ll r=1; b%=MOD; while(e){ if(e&1) r=r*b%MOD; b=b*b%MOD; e>>=1;} return r; }
inline ll C(int n,int k){ if(k<0||n<0||k>n) return 0; return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD; }
inline ll cat(int m){ return C(2*m,m)*ifac[m+1]%MOD*fac[m]%MOD; }
inline ll catInv(int m){ return (ll)(m+1)%MOD*fac[m]%MOD*fac[m]%MOD*ifac[2*m]%MOD; }
inline void addRun(int len){ if(len&1) oddCnt++; else Prod = Prod*cat(len/2)%MOD; }
inline void remRun(int len){ if(len&1) oddCnt--; else Prod = Prod*catInv(len/2)%MOD; }

template<class F> void forRuns(int L0,int R0, F f){
    auto it = bnd.find(L0-1); int prev = L0-1; ++it;
    while(true){ int e = *it; f(e-prev); if(e>=R0) break; prev=e; ++it; }
}

void flip(int i){
    int lo = max(1,i-1), hi = min(N,i+1);
    int L0 = *prev(bnd.lower_bound(lo)) + 1;
    int R0 = *bnd.lower_bound(hi);
    forRuns(L0,R0,[&](int len){ remRun(len); });
    S[i] = (S[i]=='Y' ? 'N' : 'Y');
    for(int p : {i-1, i}){
        if(p<1 || p>N-1) continue;
        if(S[p]!=S[p+1]) bnd.insert(p); else bnd.erase(p);
    }
    forRuns(L0,R0,[&](int len){ addRun(len); });
}

ll query(int K){
    ll v = (ll)N - 2LL*K;                 // 最終的な d_N
    int p = *prev(prev(bnd.end()));       // 最後の run は [p+1, N]
    int L = N - p;
    if(oddCnt - ((L&1)?1:0) > 0) return 0; // 最後以外に奇数長 run
    ll P = Prod;
    if(!(L&1)) P = P*catInv(L/2)%MOD;
    ll w = (S[N]=='Y') ? v : -v;
    if(w<0 || w>L || ((L-w)&1)) return 0;
    int a = (int)((L+w)/2);
    return P*((C(L,a)-C(L,a+1)+MOD)%MOD)%MOD;
}

int main(){
    static char buf[1<<25];
    size_t sz = fread(buf,1,sizeof(buf)-1,stdin); buf[sz]=0;
    char *ptr = buf;
    auto readInt=[&]()->int{ while(*ptr && (*ptr<'0'||*ptr>'9')) ptr++; int x=0;
        while(*ptr>='0'&&*ptr<='9') x=x*10+(*ptr++-'0'); return x; };
    N = readInt(); Q = readInt();
    while(*ptr && *ptr!='Y' && *ptr!='N') ptr++;
    for(int i=1;i<=N;i++) S[i]=*ptr++;
    S[N+1]=0;

    fac.resize(N+3); ifac.resize(N+3);
    fac[0]=1; for(int i=1;i<=N+2;i++) fac[i]=fac[i-1]*i%MOD;
    ifac[N+2]=pw(fac[N+2],MOD-2); for(int i=N+2;i>0;i--) ifac[i-1]=ifac[i]*i%MOD;

    bnd.insert(0); bnd.insert(N);
    for(int i=1;i<N;i++) if(S[i]!=S[i+1]) bnd.insert(i);
    { int prv=0; for(int e : bnd){ if(e==0) continue; addRun(e-prv); prv=e; } }

    string out;
    for(int q=0;q<Q;q++){
        int t=readInt(), x=readInt();
        if(t==1) flip(x);
        else { out += to_string(query(x)); out += '\n'; }
    }
    fwrite(out.data(),1,out.size(),stdout);
}