#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 time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
16748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
16748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
17004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
17004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
16748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
16748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
