Submission #341751

#TimeUsernameProblemLanguageResultExecution timeMemory
341751GajowyLucky Numbers (RMI19_lucky)C++14
0 / 100
70 ms17004 KiB
#include <bits/stdc++.h> using namespace std; #define size(x) (int)x.size() #define e1 first #define e2 second #define pb push_back #define eb emplace_back #define ll long long #define ld long double const int mod=1e9+7; const int N=4; void add(int &x,int v){ x+=v; if(x>=mod) x-=mod; } void sub(int &x,int v){ x-=v; if(x<0) x+=mod; } int sum(int u,int v){ return (u+v>=mod?u+v-mod:u+v); } int mul(ll a,ll b){ return (a*b)%mod; } int inv(int x){ int xp=mod-2; int res=1; while(xp){ if(xp&1) res=mul(res,x); xp/=2; if(xp) x=mul(x,x); } return res; } struct matrix{ int a[N][N]; matrix(){ for(int i=0;i<N;i++) fill(a[i],a[i]+N,0); } int* operator [](int x){ return a[x]; } matrix operator *(matrix xd){ matrix res; for(int i=0;i<N;i++) for(int k=0;k<N;k++) for(int j=0;j<N;j++) add(res[i][j],mul((*this)[i][k],xd[k][j])); return res; } matrix operator ~(){ matrix res; matrix temp=(*this); for(int i=0;i<N;i++) res[i][i]=1; for(int i=0;i<N;i++){ int row=i; while(row<N&&temp[row][i]==0) row++; if(row==N) assert("Non-invertible\n"); for(int j=0;j<N;j++) swap(temp[row][j],temp[i][j]),swap(res[row][j],res[i][j]); int rev=inv(temp[i][i]); for(int j=0;j<N;j++) temp[i][j]=mul(temp[i][j],rev),res[i][j]=mul(res[i][j],rev); for(int j=0;j<N;j++){ if(i==j) continue; int rem=temp[j][i]; for(int l=0;l<N;l++) sub(temp[j][l],mul(rem,temp[i][l])),sub(res[j][l],mul(rem,res[i][l])); } } return res; } }; string s; matrix evo[10]; matrix def; matrix neu; const int MAXN=1e5+10; const int base=(1<<17); matrix t[base*2]; int get(int l,int r){ l+=base; r+=base; matrix lres=t[l]; matrix rres; if(l!=r) rres=t[r]; else rres=neu; while(l/2!=r/2){ if(l%2==0) lres=lres*t[l+1]; if(r%2==1) rres=t[r-1]*rres; l/=2; r/=2; } matrix ans=def; ans=ans*lres; ans=ans*rres; int res=1; add(res,ans[0][0]); add(res,ans[0][1]); return res; } void update(int p,int c){ p+=base; t[p]=evo[c]; while(p/=2) t[p]=t[p*2]*t[p*2+1]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,q; cin>>n>>q; cin>>s; for(int i=0;i<10;i++){ evo[i][0][0]=1; evo[i][0][1]=8; evo[i][0][2]=0; evo[i][1][0]=1; evo[i][1][1]=9; evo[i][1][2]=0; if(i>1) evo[i][2][0]=1; evo[i][2][1]=i; if(i>1) evo[i][2][1]--; evo[i][2][2]=1; } def[0][2]=1; for(int i=0;i<N;i++) neu[i][i]=1; for(int i=0;i<n;i++) t[base+i]=evo[(int)(s[i]-'0')]; for(int i=n;i<base;i++) t[i]=neu; for(int i=base-1;i>0;i--) t[i]=t[i*2]*t[i*2+1]; cout<<get(0,n-1)<<'\n'; for(int i=0;i<q;i++){ int type; cin>>type; if(type==1){ int l,r; cin>>l>>r; l--,r--; cout<<get(l,r)<<'\n'; } else{ int p,c; cin>>p>>c; p--; update(p,c); } } }
#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...