Submission #1300535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300535		NotLinux	Lucky Numbers (RMI19_lucky)	C++20	0 / 100	873 ms	257040 KiB

lucky

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 131072;
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(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;
	}
	void print(){
		for(int i = 0;i<11;i++){
			for(int j = 0;j<11;j++){
				cout << mat[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
} iden;

vector < Matrix > t;
Matrix merge(Matrix &x , Matrix &y){
    return mult(x,y);
}
void init(){
    t.assign(2*N , iden);
}
void update(int p, Matrix value) {  // set value at position p
    for (t[p += N] = value; p > 1; p >>= 1){
        t[p>>1] = merge(t[p] , t[p^1]); 
    }
}
Matrix query(int l, int r) {  // sum on interval [l, r]
    Matrix res = iden;
    queue<Matrix>v1;
    stack<Matrix>v2;
    for (r+=1 , l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l&1) v1.push(t[l++]);
        if (r&1) v2.push(t[--r]);
    }
    while(!v1.empty()){
    	res = mult(res , v1.front());
    	v1.pop();
    }
    while(!v2.empty()){
    	res = mult(res , v2.top());
    	v2.pop();
    }
    return res;
}


// 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){
// 		cout << "carp : " << endl;
// 		tree[ind].print();
// 		return tree[ind];
// 	}
// 	else if(l > qr or r < ql)return iden;
// 	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++){
		iden.mat[i][i] = 1;
	}
	init();
    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;
    		tran.mat[10][10] = 1;
    	}
    	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 ? iden : 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;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 27
• Subtask 5: 0 / 9
• Subtask 6: 0 / 27