Submission #258148

#	Time	Username	Problem	Language	Result	Execution time	Memory
258148		lyc	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	58 ms	18036 KiB

lucky

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 1e5+5;
const int mod = 1e9+7;

int N, Q;
string X;

int f[mxN][2][2];

using Data = array<array<array<int,2>,2>,2>; // bound, start 3, end 1;
struct node {
	int s, e, m;
	Data v;
	node *l, *r;
	
	void setLeaf(char c) {
		X[s] = c;
		v[1][0][0] = (c != '3' && c != '1');
		v[1][0][1] = (c == '1');
		v[1][1][0] = (c == '3');
		v[1][1][1] = 0;
		int u = c-'0';
		v[0][0][0] = u - (c > '3') - (c > '1');
		v[0][0][1] = (c > '1');
		v[0][1][0] = (c > '3');
		v[0][1][1] = 0;
		
		//~ cout << "SET" _ s _ c << " :: ";
		//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << v[x][y][z] << ' ';
		//~ cout << endl;
	}
	
	inline Data merge(int L, int R, Data a, Data b) {
		Data u;
		int lenb = R-m;
		FOR(i,0,1){
			FOR(j,0,1){				
				u[1][i][j]  = (ll) a[1][i][0] * b[1][0][j] % mod;
				u[1][i][j] += (ll) a[1][i][0] * b[1][1][j] % mod;
				u[1][i][j] %= mod;
				u[1][i][j] += (ll) a[1][i][1] * b[1][0][j] % mod;
				u[1][i][j] %= mod;
			}
		}
		FOR(i,0,1){
			FOR(j,0,1){				
				u[0][i][j]  = (ll) a[0][i][0] * f[lenb][0][j] % mod;
				u[0][i][j] += (ll) a[0][i][0] * f[lenb][1][j] % mod;
				u[0][i][j] %= mod;
				u[0][i][j] += (ll) a[0][i][1] * f[lenb][0][j] % mod;
				u[0][i][j] %= mod;
				
				u[0][i][j] += (ll) a[1][i][0] * b[0][0][j] % mod;
				u[0][i][j] %= mod;
				u[0][i][j] += (ll) a[1][i][0] * b[0][1][j] % mod;
				u[0][i][j] %= mod;
				u[0][i][j] += (ll) a[1][i][1] * b[0][0][j] % mod;
				u[0][i][j] %= mod;
			}
		}
		
		//~ cout << "MERGE" _ L _ R << " :: ";
		//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << u[x][y][z] << ' ';
		//~ cout << endl;
		return u;
	}
		
	node(int s, int e): s(s), e(e), m((s+e)/2) {
		if (s == e) setLeaf(X[s]);
		else {
			l = new node(s,m), r = new node(m+1,e);
			v = merge(s,e,l->v,r->v);
		}
		
		//~ cout << s _ e << " :: ";
		//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << v[x][y][z] << ' ';
		//~ cout << endl;
	}
	
	void update(int a, char b) {
		if (s == e) { setLeaf(b); return; }
		else if (a <= m) l->update(a,b);
		else r->update(a,b);
		v = merge(s,e,l->v,r->v);
	}
	
	Data query(int a, int b) {
		if (s == a && e == b) return v;
		if (b <= m) return l->query(a,b);
		if (a > m) return r->query(a,b);
		return merge(a, b, l->query(a,m), r->query(m+1,b));
	}
} *root;

void answer(int L, int R) {
	Data res = root->query(L,R);
	int ans = 0;
	//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << res[x][y][z] << ' ';
	//~ cout << " :: ";
	FOR(a,0,1) FOR(b,0,1) FOR(c,0,1) ans = (ans+res[a][b][c])%mod;
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> N >> Q >> X;
	X = '^' + X;
	
	f[0][0][0] = 1;
	f[0][0][1] = f[0][1][0] = f[0][1][1] = 0;
	f[1][0][0] = 8;
	f[1][0][1] = f[1][1][0] = 1;
	f[1][1][1] = 0;
	FOR(i,2,N){
		f[i][0][0]  = (ll) f[i-1][0][0] * 9 % mod;
		f[i][0][0] += (ll) f[i-1][0][1] * 8 % mod;
		f[i][0][0] %= mod;
		f[i][0][1]  = (f[i-1][0][0] + f[i-1][0][1]) % mod;
		
		f[i][1][0]  = (ll) f[i-1][1][0] * 9 % mod;
		f[i][1][0] += (ll) f[i-1][1][1] * 8 % mod;
		f[i][1][0] %= mod;
		f[i][1][1]  = (f[i-1][1][0] + f[i-1][1][1]) % mod;
	}
	root = new node(1,N);
	
	//~ int ans = 0;
	//~ FOR(x,0,1) FOR(y,0,1) {
		//~ ans += f[N][x][y];
		//~ cout << f[N][x][y] << ' ';
	//~ }
	//~ cout << " :: " << ans << endl;
	
	answer(1,N);
	FOR(i,1,Q){
		int T; cin >> T;
		if (T == 1) {
			int L, R; cin >> L >> R;
			//~ TRACE(T _ L _ R);
			answer(L,R);
		} else {
			int P; char D; cin >> P >> D;
			root->update(P,D);
		}
	}
}

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