結果

問題 No.2762 Counting and Deleting
ユーザー nononnonon
提出日時 2024-05-18 07:51:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,202 ms / 4,000 ms
コード長 6,493 bytes
コンパイル時間 2,679 ms
コンパイル使用メモリ 234,400 KB
実行使用メモリ 42,088 KB
最終ジャッジ日時 2024-05-18 07:51:36
合計ジャッジ時間 14,871 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1,064 ms
41,856 KB
testcase_08 AC 1,067 ms
42,000 KB
testcase_09 AC 1,089 ms
42,052 KB
testcase_10 AC 1,084 ms
41,904 KB
testcase_11 AC 1,202 ms
42,012 KB
testcase_12 AC 1,150 ms
42,088 KB
testcase_13 AC 1,176 ms
41,860 KB
testcase_14 AC 1,166 ms
42,008 KB
testcase_15 AC 915 ms
41,948 KB
testcase_16 AC 920 ms
41,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/segtree>
#include<atcoder/modint>
using namespace std;
template<typename mint>
struct matrix
{
public:
    int row,col;
    matrix(int row, int col)
    {
        this->row=row;
        this->col=col;
        this->A.resize(row);
        for(int i=0;i<row;i++)this->A[i].resize(col);
    }
    matrix(const vector<vector<mint>>&v)
    {
        this->row=v.size();
        this->col=v[0].size();
        A.resize(row);
        for(int i=0;i<row;i++)
        {
            A[i].resize(col);
            for(int j=0;j<col;j++)A[i][j]=v[i][j];
        }
    }
    matrix(vector<vector<matrix>> M)
    {
        int n=M.size(),m=M[0].size();
        int r=M[0][0].row,c=M[0][0].col;
        row=n*r,col=m*c;
        A.resize(row);
        for(int i=0;i<row;i++)
        {
            A[i].resize(col);
            for(int j=0;j<col;j++)
            {
                A[i][j]=M[i/r][j/c][i%r][j%c];
            }
        }
    }
    vector<mint>&operator[](int p){return this->A[p];}
    const vector<mint>&operator[](int p)const{return this->A[p];}
    matrix& operator+=(const matrix& B)
    {
        assert(B.row==row);
        assert(B.col==col);
        B.col=1;
        for(int i=0;i<row;i++)for(int j=0;j<col;j++)
        {
            this->A[i][j]+=B[i][j];
        }
        return *this;
    }
    matrix& operator-=(const matrix& B)
    {
        assert(B.row==row);
        assert(B.col==col);
        for(int i=0;i<this->row;i++)for(int j=0;j<this->col;j++)
        {
            this->A[i][j]-=B[i][j];
        }
        return *this;
    }
    matrix& operator*=(const matrix& B)
    {
        assert(row==col);
        assert(B.row==row);
        assert(B.col==col);
        matrix res(row,row);
        for(int i=0;i<row;i++)for(int k=0;k<row;k++)for(int j=0;j<row;j++)
        {
            res[i][j]+=this->A[i][k]*B[k][j];
        }
        return *this=res;
    }
    matrix operator*(const matrix& B)const
    {
        assert(B.row==col);
        matrix res(row,B.col);
        for(int i=0;i<row;i++)for(int k=0;k<col;k++)for(int j=0;j<B.col;j++)
        {
            res[i][j]+=this->A[i][k]*B[k][j];
        }
        return res;
    }
    matrix& operator*=(const mint& r)
    {
        for(int i=0;i<row;i++)for(int j=0;j<col;j++)
        {
            this->A[i][j]*=r;
        }
        return *this;
    }
    matrix& operator/=(const mint& r)
    {
        mint inv=mint(r).inv();
        (*this)*=inv;
        return *this;
    }
    matrix operator+(const matrix& B)const{return matrix(*this)+=B;}
    matrix operator-(const matrix &B)const{return matrix(*this)-=B;}
    matrix operator*(const mint& r)const{return matrix(*this)*=r;}
    matrix operator/(const mint& r)const{return matrix(*this)/=r;}
    bool operator==(const matrix& B)const
    {
        if(row!=B.row||col!=B.col)return 0;
        for(int i=0;i<row;i++)for(int j=0;j<col;j++)if(A[i][j]!=B[i][j])return 0;
        return 1;
    }
    bool operator!=(const matrix& B)const
    {
        if(row!=B.row||col!=B.col)return 1;
        for(int i=0;i<row;i++)for(int j=0;j<col;j++)if(A[i][j]!=B[i][j])return 1;
        return 0;
    }
    static constexpr matrix I(int n)
    {
        matrix res(n,n);
        for(int i=0;i<n;i++)res[i][i]=mint::raw(1);
        return res;
    }
    static constexpr matrix O(int n, int m)
    {
        return matrix(n,m);
    }
    matrix pow(long long k)const
    {
        assert(row==col);
        matrix B=*this;
        matrix res=I(row);
        while(k)
        {
            if(k&1)res*=B;
            B*=B;
            k>>=1;
        }
        return res;
    }
    mint det()const
    {
        assert(row==col);
        int cnt=0;
        matrix B=*this;
        for(int i=0;i<row;i++)
        {
            for(int j=i;j<row;j++)if(B[j][i]!=0)
            {
                swap(B[i],B[j]);
                cnt+=j!=i;
                break;
            }
            for(int j=i+1;j<row;j++)
            {
                if(B[i][i]==0)continue;
                mint inv=B[i][i].inv();
                inv*=B[j][i];
                for(int k=i+1;k<row;k++)B[j][k]-=B[i][k]*inv;
            }
        }
        mint res=1;
        for(int i=0;i<row;i++)res*=B[i][i];
        if(cnt&1)res*=-1;
        return res;
    }
    matrix inv()const
    {
        assert(row==col);
        assert(this->det()!=0);
        matrix B=*this;
        matrix invB=I(row);
        for(int i=0;i<row;i++)
        {
            if(B[i][i]==0)
            {
                for(int j=i+1;j<row;j++)if(B[j][i]!=0)
                {
                    swap(B[i],B[j]);
                    swap(invB[i],invB[j]);
                    break;
                }
            }
            mint cef=B[i][i].inv();
            for(int j=0;j<row;j++)
            {
                B[i][j]*=cef;
                invB[i][j]*=cef;
            }
            for(int j=0;j<row;j++)if(i!=j)
            {
                cef=B[j][i];
                for(int k=0;k<row;k++)
                {
                    B[j][k]-=B[i][k]*cef;
                    invB[j][k]-=invB[i][k]*cef;
                }
            }
        }
        return invB;
    }
    matrix T()const
    {
        matrix res(col,row);
        for(int i=0;i<row;i++)for(int j=0;j<col;j++)res[j][i]=A[i][j];
        return res;
    }
    void print()
    {
        for(int i=0;i<row;i++)for(int j=0;j<col;j++)cout<<A[i][j].val()<<" \n"[j+1==col];
    }
private:
    vector<vector<mint>>A;
};
using mint=atcoder::modint998244353;
using mat=matrix<mint>;
const mat I=mat::I(3);
const mat zero=vector<vector<mint>>{{1,1,0},{0,1,0},{0,0,1}};
const mat one=vector<vector<mint>>{{1,0,0},{1,1,1},{0,0,1}};
mat op(mat a, mat b){return a*b;}
mat e(){return I;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin>>N>>Q;
    atcoder::segtree<mat,op,e>seg(N);
    set<int>bar;
    for(int i=0;i<N;i++)bar.insert(i);
    string S;
    cin>>S;
    reverse(S.begin(),S.end());
    for(int i=0;i<N;i++)seg.set(i,S[i]=='0'?zero:one);
    for(;Q--;)
    {
        int t,l,r;
        cin>>t>>l>>r;
        int L=N-r,R=N-l+1;
        if(t==1)
        {
            auto it=bar.lower_bound(L);
            while(it!=bar.end()&&*it<R)
            {
                seg.set(*it,I);
                it=bar.erase(it);
            }
        }
        else
        {
            auto M=seg.prod(L,R);
            cout<<(M[0][2]+M[1][2]).val()<<'\n';
        }
    }
}
0