Submission #258109

#	Time	Username	Problem	Language	Result	Execution time	Memory
258109		oolimry	Lucky Numbers (RMI19_lucky)	C++14	14 / 100	4 ms	2688 KiB

lucky

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define int long long
using namespace std;
typedef pair<int,int> ii;

///1 is tail (one)
///3 is head (three)
int mod = 1000000007;

void fix(int &x){
	x %= mod;
	if(x < 0) x += mod;
}

int arr[100005];
int ten[100005];

struct data{
	int cnt = 0;
	int cnttail = 0;
	int cnthead = 0;
	int cntboth = 0;
	int len = 1;
	
	bool isHead = false;
	bool isTail = false;
	bool isOk = true;
};

void out(data D){
	cout << "ways : " << D.cnt << "\n";
	cout << "waysHead : " << D.cnthead << "\n";
	cout << "waysTail : " << D.cnttail << "\n";
	cout << "waysBoth : " << D.cntboth << "\n";
	cout << "len : " << D.len << "\n\n";
}

data basic(int x){
	data val;
	val.cnt = x;
	
	if(x > 1){
		val.cnttail = 1;
	}
	if(x > 3){
		val.cnthead = 1;
	}
	if(x == 1) val.isTail = true;
	if(x == 3) val.isHead = true;
	
	return val;
}

inline int ways(int digits){
	int ans = ten[digits];
	if(digits >= 2) ans -= ten[digits-2] * (digits-1);
	fix(ans);
	return ans;
}

data merge(data l, data r){
	data val;
	
	///consider when l is not bounded
	val.cnt = l.cnt * ways(r.len);
	val.cnt -= l.cnttail * ways(r.len-1);
	fix(val.cnt);
	
	val.cnttail = l.cnt * ways(r.len-1);
	if(r.len >= 2) val.cnttail -= l.cnttail * ways(r.len-2);
	fix(val.cnttail);
	
	val.cnthead = l.cnthead * ways(r.len);
	val.cnthead -= l.cntboth * ways(r.len-1);
	fix(val.cnthead);
	
	val.cntboth = l.cnthead * ways(r.len-1);
	if(r.len >= 2) val.cntboth -= l.cntboth * ways(r.len-2); 
	fix(val.cntboth);
	
	///when l is bounded
	if(l.isOk){
		if(l.isHead){
			val.cnthead += r.cnthead;
			if(l.isTail) val.cnthead -= r.cnthead;
			fix(val.cnthead);
			
			val.cntboth += r.cntboth;
			if(l.isTail) val.cntboth -= r.cntboth;
			fix(val.cnttail);
		}
		
		val.cnt += r.cnt;
		if(l.isTail) val.cnt -= r.cnthead;
		fix(val.cnt);
		
		val.cnttail += r.cnttail;
		if(l.isTail) val.cnttail -= r.cntboth;
		fix(val.cntboth);
	}	
	
	val.len = l.len + r.len;
	val.isHead = l.isHead;
	val.isTail = r.isTail;
	val.isOk = (l.isOk && r.isOk);
	if(l.isTail && r.isHead) val.isOk = false;
	
	return val;
}

struct node{
	
	int s, e, m;
	data val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E; m =(s+e)/2;
		if(s == e){
			val = basic(arr[s]);
		//	cout << s << " " << e << ":\n";
			//out(val);
		}
		else{
			l = new node(s,m);
			r = new node(m+1,e);
			val = merge(l->val, r->val);
			//cout << s << " " << e << ":\n";
			//out(val);
		}
	}
	
	void update(int s, int x){
		if(s == e){
			val = basic(x);
			return;
		}
		if(s <= m) l->update(s,x);
		else r->update(s,x);
		
		val = merge(l->val, r->val);
	}
	
	
	data query(int S, int E){
		if(s == S && e == E){
			return val;
		}
		else if(E <= m) return l->query(S,E);
		else if(S >= m+1) return r->query(S,E);
		else return merge(l->query(S,m), r->query(m+1,E));
	}
	
} *root;



signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	
	string s; cin >> s;
	for(int i = 0;i < n;i++){
		arr[i] = (s[i] - '0');
	}
	
	ten[0] = 1;
	for(int i = 1;i <= 100000;i++){
		ten[i] = ten[i-1] * 10;
		fix(ten[i]);
	}
	
	root = new node(0,n-1);
	
	
	data D = root->val;
	int ans = D.cnt;
	if(D.isOk) ans++;
	fix(ans);
	cout << ans;
}

/*
 * 
def cnt(x):
	a = 0
	b = 0
	c = 0
	d = 0
	for i in range(0,x):
		s = str(i)
		a += 1
		if s[0] == '3':
			b += 1
		if s[-1] == '1':
			c += 1
		if s[0] == '3' and s[-1] == '1':
			d += 1
	print(a)
	print(b)
	print(c)
	print(d)
*/

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