| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1300502 | NotLinux | Lucky Numbers (RMI19_lucky) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
inline void ckadd(int &a , int b){
a += b;
if(a >= mod)a -= mod;
}
struct Matrix{
vector<vector<int>>mat;
Matrix(){
mat.assign(11,vector<int>(11,0));
}
friend Matrix mult(Matrix &a , Matrix &b){
Matrix c;
for(int i = 0;i<11;i++){
for(int j = 0;j<11;j++){
for(int k = 0;k<11;k++){
ckadd(c.mat[i][j] , 1LL * a.mat[i][k] * b.mat[k][j] % mod);
}
}
}
return c;
}
} identity;
vector<Matrix>tree(4*N+7);
void update(int qp , Matrix &qv , int ind=1 , int l=0 , int r=N-1){
if(l == r){
tree[ind] = qv;
return;
}
int mid = (l + r) / 2;
if(qp <= mid)update(qp , qv , ind*2 , l , mid);
else update(qp , qv , ind*2+1 , mid+1 , r);
tree[ind] = mult(tree[ind*2] , tree[ind*2+1]);
}
Matrix query(int ql , int qr , int ind=1 , int l=0 , int r=N-1){
if(l >= ql and r <= qr)return tree[ind];
else if(l > qr or r < ql)return identity;
int mid = (l + r) / 2;
Matrix A = query(ql,qr,ind*2,l,mid);
Matrix B = query(ql,qr,ind*2+1,mid+1,r);
return mult(A,B);
}
void solve(){
for(int i = 0;i<11;i++){
identity.mat[i][i] = 1;
}
int n,q;
cin >> n >> q;
string str;
cin >> str;
auto upd = [&](int p , int x){// p yi x yap
Matrix tran;
if(x == 3 and p > 0 and str[p-1] == '1'){
for(int i = 0;i<10;i++)
for(int j = 0;j<10;j++)
tran.mat[i][j] = 1;
tran.mat[1][3] = 0;
for(int i = 0;i<x;i++){
tran.mat[10][i] = 1;
}
}
else if(p > 0 and str[p-1] == '1'){
for(int i = 0;i<10;i++)
for(int j = 0;j<10;j++)
tran.mat[i][j] = 1;
tran.mat[1][3] = 0;
for(int i = 0;i<x;i++){
tran.mat[10][i] = 1;
}
tran.mat[10][3] = 0;
}
else{
for(int i = 0;i<10;i++)
for(int j = 0;j<10;j++)
tran.mat[i][j] = 1;
tran.mat[1][3] = 0;
for(int i = 0;i<x;i++){
tran.mat[10][i] = 1;
}
tran.mat[10][10] = 1;
}
update(p , tran);
};
auto que = [&](int l , int r){
Matrix st;
for(int i = 0;i<str[l] - '0';i++)st.mat[0][i] = 1;
st.mat[0][10] = 1;
Matrix res = l == r ? identity : query(l+1 , r);
st = mult(st , res);
int ans = 0;
for(int i = 0;i<=10;i++){
ckadd(ans , st.mat[0][i]);
}
return ans;
};
for(int i = 0;i<n;i++){
upd(i , str[i] - '0');
}
cout << que(0,n-1) << endl;
while(q--){
int typ;
cin >> typ;
if(typ == 1){
int l,r;
cin >> l >> r;
l-- , r--;
cout << que(l,r) << endl;
}
else{
int p,x;
cin >> p >> x;
p--;
upd(p , x);
str[p] = '0' + x;
}
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase=1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}