Submission #2260

#	Time	Username	Problem	Language	Result	Execution time	Memory
2260		kriii	생일수 II (GA4_birthday2)	C++98	100 / 100	62 ms	13232 KiB

birthday2

#include <iostream>
#include <string>
using namespace std;

const long long mod = 19980305;
long long linear[200020];
long long scalar[200020];
long long sum[200020];
long long ten[200020],cnt[200020];
long long three[200020];
long long eight[200020];

void add(long long &a, long long p){a = (a + p) % mod;}
void mul(long long &a, long long p){a = (a * p) % mod;}

long long get(string s)
{
	int i,l=s.length()-1;
	long long res = sum[l];
	long long in = 0, p, c;

	for (i=0;i<s.length();i++,l--){
		p = ten[l]; c = (cnt[l] + mod - 1) % mod;
		if (s[i] == '3'){
			in += 3 * p;
		}
		if (s[i] == '5'){
			add(res,(in+3*p)*(in+3*p)%mod*c%mod);
			add(res,(linear[l]*2+mod*2-three[l]-eight[l])%mod*(in+3*p)%mod);
			add(res,scalar[l]);
			add(res,(in+3*p+eight[l])*(in+5*p+three[l])%mod);

			in += 5 * p;
		}
		if (s[i] == '8'){
			add(res,(in+3*p)*(in+3*p)%mod*c%mod);
			add(res,(linear[l]*2+mod*2-three[l]-eight[l])%mod*(in+3*p)%mod);
			add(res,scalar[l]);
			add(res,(in+3*p+eight[l])*(in+5*p+three[l])%mod);

			add(res,(in+5*p)*(in+5*p)%mod*c%mod);
			add(res,(linear[l]*2+mod*2-three[l]-eight[l])%mod*(in+5*p)%mod);
			add(res,scalar[l]);
			add(res,(in+5*p+eight[l])*(in+8*p+three[l])%mod);
			
			in += 8 * p;
		}
		in %= mod;
	}

	return res;
}

int main()
{
	int i;

	ten[0] = cnt[0] = 1; three[0] = eight[0] = 0;
	for (i=1;i<=200000;i++){
		ten[i] = ten[i-1] * 10 % mod;
		cnt[i] = cnt[i-1] * 3 % mod;
		three[i] = (three[i-1] * 10 + 3) % mod;
		eight[i] = (eight[i-1] * 10 + 8) % mod;
	}

	long long p;
	linear[0] = 0; p = 16;
	for (i=1;i<=200000;i++){
		linear[i] = linear[i-1] * 3 % mod;
		add(linear[i],p);
		mul(p,30);
	}

	scalar[1] = 55;
	for (i=2;i<=200000;i++){
		p = ten[i-1];
		scalar[i] = 0;
		add(scalar[i],(cnt[i-1]+mod-1)*(9+25+64)%mod*p%mod*p%mod);
		add(scalar[i],(linear[i-1]*2+mod*2-three[i-1]-eight[i-1])*(3+5+8)%mod*p%mod);
		add(scalar[i],(scalar[i-1]*3)%mod);
		add(scalar[i],(3*p+eight[i-1])*(5*p+three[i-1])%mod);
		add(scalar[i],(5*p+eight[i-1])*(8*p+three[i-1])%mod);
	}

	for (i=1;i<=200000;i++){
		sum[i] = sum[i-1];
		add(sum[i],three[i+1]*eight[i]%mod);
		add(sum[i],scalar[i]);
	}

	string a,b;
	cin >> a >> b;
	cout << (get(b) - get(a) + mod) % mod << endl;

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30