結果
| 問題 |
No.2762 Counting and Deleting
|
| コンテスト | |
| ユーザー |
 nonon
|
| 提出日時 | 2024-05-18 07:51:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,407 ms / 4,000 ms |
| コード長 | 6,493 bytes |
| コンパイル時間 | 2,853 ms |
| コンパイル使用メモリ | 226,588 KB |
| 最終ジャッジ日時 | 2025-02-21 15:40:33 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 |
ソースコード
#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';
}
}
}