Submission #341758

#	Time	Username	Problem	Language	Result	Execution time	Memory
341758		Gajowy	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	103 ms	17388 KiB

lucky

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27