結果

問題 No.2611 Count 01
ユーザー 沙耶花
提出日時 2024-01-19 22:17:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,381 ms / 6,000 ms
コード長 2,025 bytes
コンパイル時間 4,314 ms
コンパイル使用メモリ 256,664 KB
最終ジャッジ日時 2025-02-18 21:11:55
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000001
using A = array<array<mint,4>,5>;
A e(){
    A ret;
    rep(i,5){
        rep(j,4){
            ret[i][j] = 0;
        }
    }
    return ret;
}
A op(A a,A b){
    if(a==e())return b;
    if(b==e())return a;
    A ret = e();
    rep(i,4){
        rep(j,4){
            if(j&i)continue;
            int k = (i|j);
            rep(l,5){
                rep(m,5){
                    //cout<<k<<endl;
                    int n = 0;
                    if(l==0){
                        if(m==0)n = 0;
                        if(m==1)n = 4;
                        if(m==2)n = 2;
                        if(m==3)n = 2;
                        if(m==4)n = 4;
                    }
                    if(l==1){
                        if(m==0)n = 1;
                        if(m==1)continue;
                        if(m==2)continue;
                        if(m==3)continue;
                        if(m==4)continue;
                    }
                    if(l==2){
                        if(m==0)n = 4;
                        if(m==1)n = 4;
                        if(m==2)continue;
                        if(m==3)n = 2;
                        if(m==4)continue;
                    }
                    if(l==3){
                        if(m==0)n = 1;
                        if(m==1)n = 1;
                        if(m==2)continue;
                        if(m==3)n = 3;
                        if(m==4)continue;
                    }
                    if(l==4){
                        if(m==0)n = 4;
                        else continue;
                    }
                    ret[n][k] += a[l][i] * b[m][j];
                }
            }
        }
    }
    return ret;
}
int main(){
    
    int n,q;
    cin>>n>>q;
    vector<A> t(n);
    string s;
    cin>>s;
    rep(i,n){
        A temp = e();
        temp[0][0] = 1;
        temp[3][1<<(s[i]-'0')] ++;
        temp[3][0] ++;
        t[i] = temp;
        
    }
    /*auto ret = op(t[0],t[1]);
    
    rep(i,5){
                rep(j,4){
                    cout<<ret[i][j].val()<<' ';
                }
                cout<<endl;
            }
    return 0;
    */
    segtree<A,op,e> seg(t);
    rep(_,q){
        int x;
        cin>>x;
        if(x==1){
            int ii;
            cin>>ii;
            ii--;
            s[ii] ^= 1;
            A temp = e();
            temp[0][0] = 1;
            temp[3][1<<(s[ii]-'0')] ++;
            temp[3][0] ++;
            seg.set(ii,temp);
        }
        else{
            int l,r;
            cin>>l>>r;
            l--;
            auto ret = seg.prod(l,r);
            mint ans = 0;
            rep(i,5)ans += ret[i][3];
            /*rep(i,5){
                rep(j,4){
                    cout<<ret[i][j].val()<<' ';
                }
                cout<<endl;
            }*/
            cout<<ans.val()<<endl;
        }
    }
        
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0