oj.uz

Submission #341758

# Submission time Handle Problem Language Result Execution time Memory
341758 2020-12-30T23:24:16 Z Gajowy Lucky Numbers (RMI19_lucky) C++14
100 / 100
 103 ms 17388 KB 
#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=0;
	for(int i=0;i<N;i++)
		add(res,ans[0][i]);
	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++){
		int x=i;
		evo[i][0][0]=1;
		evo[i][0][1]=0;
		evo[i][0][2]=8;
		evo[i][0][3]=0;
		
		evo[i][1][0]=(x>1?1:0);
		evo[i][1][1]=(x==1?1:0);
		evo[i][1][2]=x-(x>1?1:0)-(x>3?1:0);
		evo[i][1][3]=((x!=1&&x!=3)?1:0);

		evo[i][2][0]=1;
		evo[i][2][1]=0;
		evo[i][2][2]=9;
		evo[i][2][3]=0;

		evo[i][3][0]=(x>1?1:0);
		evo[i][3][1]=(x==1?1:0);
		evo[i][3][2]=x-(x>1?1:0);
		evo[i][3][3]=(x!=1?1:0);
	}
	def[0][3]=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];
	/*for(int i=0;i<n-1;i++)
		cout<<get(0,i)<<'\n';*/
	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);
		}
	}
	/*matrix test=def;
	for(int pos=0;pos<n;pos++){
		cout<<'\n';
		test=test*t[base+pos];
		cout<<"test: "<<'\n';
		for(int i=0;i<N;i++){
			cout<<'\n';
			for(int j=0;j<N;j++)
				cout<<test[i][j]<<' ';
		}
		cout<<"muld: "<<'\n';
		for(int i=0;i<N;i++){
			cout<<'\n';
			for(int j=0;j<N;j++)
				cout<<t[pos+base][i][j]<<' ';
		}
		cout<<'\n';
	}*/
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16748 KB Output is correct
2 Correct 41 ms 16768 KB Output is correct
3 Correct 41 ms 16876 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16748 KB Output is correct
2 Correct 41 ms 16768 KB Output is correct
3 Correct 41 ms 16876 KB Output is correct
4 Correct 49 ms 16748 KB Output is correct
5 Correct 49 ms 16748 KB Output is correct
6 Correct 41 ms 16768 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16876 KB Output is correct
2 Correct 76 ms 17024 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16876 KB Output is correct
2 Correct 76 ms 17024 KB Output is correct
3 Correct 82 ms 17260 KB Output is correct
4 Correct 79 ms 17260 KB Output is correct
5 Correct 83 ms 17332 KB Output is correct
6 Correct 88 ms 17260 KB Output is correct
7 Correct 91 ms 17368 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16748 KB Output is correct
2 Correct 41 ms 16768 KB Output is correct
3 Correct 41 ms 16876 KB Output is correct
4 Correct 49 ms 16748 KB Output is correct
5 Correct 49 ms 16748 KB Output is correct
6 Correct 41 ms 16768 KB Output is correct
7 Correct 70 ms 16876 KB Output is correct
8 Correct 76 ms 17024 KB Output is correct
9 Correct 76 ms 16960 KB Output is correct
10 Correct 79 ms 17004 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16748 KB Output is correct
2 Correct 41 ms 16768 KB Output is correct
3 Correct 41 ms 16876 KB Output is correct
4 Correct 49 ms 16748 KB Output is correct
5 Correct 49 ms 16748 KB Output is correct
6 Correct 41 ms 16768 KB Output is correct
7 Correct 70 ms 16876 KB Output is correct
8 Correct 76 ms 17024 KB Output is correct
9 Correct 82 ms 17260 KB Output is correct
10 Correct 79 ms 17260 KB Output is correct
11 Correct 83 ms 17332 KB Output is correct
12 Correct 88 ms 17260 KB Output is correct
13 Correct 91 ms 17368 KB Output is correct
14 Correct 76 ms 16960 KB Output is correct
15 Correct 79 ms 17004 KB Output is correct
16 Correct 77 ms 17132 KB Output is correct
17 Correct 81 ms 17260 KB Output is correct
18 Correct 85 ms 17260 KB Output is correct
19 Correct 103 ms 17260 KB Output is correct
20 Correct 90 ms 17388 KB Output is correct