結果

問題 No.2762 Counting and Deleting
ユーザー kotatsugame
提出日時 2024-05-17 21:51:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 170 ms / 4,000 ms
コード長 1,630 bytes
コンパイル時間 1,213 ms
コンパイル使用メモリ 92,540 KB
実行使用メモリ 12,872 KB
最終ジャッジ日時 2024-12-20 13:37:46
合計ジャッジ時間 4,006 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include<iostream>
#include<set>
#include<cassert>
#include<atcoder/segtree>
#include<atcoder/modint>
using namespace std;
#include<array>
template<typename T,unsigned int N>
struct Matrix{
    array<array<T,N>,N>dat;
    array<T,N>&operator[](int i){return dat[i];}
    const array<T,N>&operator[](int i)const{return dat[i];}
    Matrix(){for(int i=0;i<N;i++)dat[i].fill(T(0));}
    static Matrix eye(){
        Matrix res;
        for(int i=0;i<N;i++)res[i][i]=1;
        return res;
    }
    Matrix operator+(const Matrix&A)const{
        Matrix res;
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)
            res[i][j]=dat[i][j]+A[i][j];
        return res;
    }
    Matrix operator*(const Matrix&A)const{
        Matrix res;
        for(int i=0;i<N;i++)for(int k=0;k<N;k++)for(int j=0;j<N;j++)
            res[i][j]+=dat[i][k]*A[k][j];
        return res;
    }
    Matrix pow(long long n)const{
        Matrix a=*this,res=eye();
        for(;n;a=a*a,n>>=1)if(n&1)res=res*a;
        return res;
    }
};
using mint=atcoder::modint998244353;
using mat=Matrix<mint,3>;
mat op(mat a,mat b){return a*b;}
mat e(){return mat::eye();}
set<int>rest;
mat U,A,B;
int N,Q;
string S;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    U=mat::eye();
    A[0][2]=1;
    A[1][1]=1;
    A[2][2]=2;A[2][0]=-1;
    B[0][0]=1;
    B[1][2]=1;
    B[2][2]=2;B[2][1]=-1;
    cin>>N>>Q>>S;
    vector<mat>init(N);
    for(int i=0;i<N;i++)
    {
        rest.insert(i);
        init[i]=S[i]=='0'?A:B;
    }
    atcoder::segtree<mat,op,e>seg(init);
    for(;Q--;)
    {
        int T,l,r;cin>>T>>l>>r;l--;
        if(T==1)
        {
            auto it=rest.lower_bound(l);
            while(it!=rest.end()&&*it<r)
            {
                seg.set(*it,U);
                it=rest.erase(it);
            }
        }
        else
        {
            mat ret=seg.prod(l,r);
            cout<<ret[1][2].val()<<"\n";
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0