제출 #199046

#제출 시각아이디문제언어결과실행 시간메모리
199046Andrei_CotorLucky Numbers (RMI19_lucky)C++14
28 / 100
17 ms1144 KiB
//aparent substring e subsecventa, nu subsir #include<iostream> #define MOD 1000000007 using namespace std; class dynamic { public: int Dp[2][2],len; //prima-pe primu 3, a doua-pe ultimu 1 int st,dr; bool eq; //posibil ca nr sa fie egal cu cel din secventa void init(int x) { Dp[0][0]=Dp[0][1]=Dp[1][0]=Dp[1][1]=0; len=1; eq=1; int nr=0; if(x>1) { nr++; Dp[0][1]=1; } if(x>3) { nr++; Dp[1][0]=1; } Dp[0][0]=x-nr; } int get_val() { int rez=0; for(int i=0; i<=1; i++) for(int j=0; j<=1; j++) rez=(rez+Dp[i][j])%MOD; if(eq) rez=(rez+1)%MOD; return rez; } }; int Nr[100005][2][2]; int Val[100005]; void comb(dynamic &A, dynamic B) { dynamic aux; aux.Dp[0][0]=aux.Dp[0][1]=aux.Dp[1][0]=aux.Dp[1][1]=0; aux.len=A.len+B.len; aux.st=A.st; aux.dr=B.dr; aux.eq=A.eq&B.eq; if(Val[A.dr]==1 && Val[B.st]==3) aux.eq=0; //A<, B-oricat for(int i=0; i<=1; i++) { for(int j=0; j<=1; j++) { for(int ii=0; ii<=1; ii++) { for(int jj=0; jj<=1; jj++) { if(j==1 && ii==1) continue; aux.Dp[i][jj]=(aux.Dp[i][jj]+((1LL*A.Dp[i][j]*Nr[B.len][ii][jj])%MOD))%MOD; } } } } //A=, B< if(!A.eq) return; for(int i=0; i<=1; i++) { for(int j=0; j<=1; j++) { if(Val[A.dr]==1 && i==1) continue; aux.Dp[Val[A.st]==3][j]=(aux.Dp[Val[A.st]==3][j]+B.Dp[i][j])%MOD; } } A=aux; } dynamic Aint[400005]; void build(int nod, int st, int dr) { if(st==dr) { Aint[nod].init(Val[st]); Aint[nod].st=st; Aint[nod].dr=dr; return; } int mij=(st+dr)/2; build(2*nod,st,mij); build(2*nod+1,mij+1,dr); Aint[nod]=Aint[2*nod]; comb(Aint[nod],Aint[2*nod+1]); } void update(int nod, int st, int dr, int poz, int val) { if(st==dr) { Val[st]=val; Aint[nod].init(val); return; } int mij=(st+dr)/2; if(poz<=mij) update(2*nod,st,mij,poz,val); else update(2*nod+1,mij+1,dr,poz,val); Aint[nod]=Aint[2*nod]; comb(Aint[nod],Aint[2*nod+1]); } dynamic rez; bool primu; void query(int nod, int st, int dr, int l, int r) { if(l<=st && dr<=r) { if(primu) { primu=false; rez=Aint[nod]; } else comb(rez,Aint[nod]); return; } int mij=(st+dr)/2; if(l<=mij) query(2*nod,st,mij,l,r); if(mij<r) query(2*nod+1,mij+1,dr,l,r); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,q; cin>>n>>q; for(int i=1; i<=n; i++) { char c; cin>>c; Val[i]=c-'0'; } Nr[0][0][0]=1; for(int i=1; i<=n; i++) { for(int c=0; c<=9; c++) { if(c==1) { Nr[i][0][1]=(Nr[i][0][1]+((Nr[i-1][0][0]+Nr[i-1][0][1])%MOD))%MOD; Nr[i][1][1]=(Nr[i][1][1]+((Nr[i-1][1][1]+Nr[i-1][1][0])%MOD))%MOD; } else if(c==3) { if(i==1) Nr[i][1][0]=1; else { Nr[i][0][0]=(Nr[i][0][0]+Nr[i-1][0][0])%MOD; Nr[i][1][0]=(Nr[i][1][0]+Nr[i-1][1][0])%MOD; } } else { Nr[i][0][0]=(Nr[i][0][0]+((Nr[i-1][0][0]+Nr[i-1][0][1])%MOD))%MOD; Nr[i][1][0]=(Nr[i][1][0]+((Nr[i-1][1][0]+Nr[i-1][1][1])%MOD))%MOD; } } } build(1,1,n); primu=true; query(1,1,n,1,n); cout<<rez.get_val()<<"\n"; for(int i=1; i<=q; i++) { int tip,x,y; cin>>tip>>x>>y; if(tip==1) { primu=true; query(1,1,n,x,y); cout<<rez.get_val()<<"\n"; } else update(1,1,n,x,y); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...