Submission #2260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2260	2013-07-20T17:46:07 Z	kriii	생일수 II (GA4_birthday2)	C++	100 / 100	62 ms	13232 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	12320 KB	Output is correct
2	Correct	22 ms	12320 KB	Output is correct
3	Correct	20 ms	12320 KB	Output is correct
4	Correct	20 ms	12320 KB	Output is correct
5	Correct	18 ms	12320 KB	Output is correct
6	Correct	19 ms	12320 KB	Output is correct
7	Correct	22 ms	12320 KB	Output is correct
8	Correct	19 ms	12320 KB	Output is correct
9	Correct	19 ms	12320 KB	Output is correct
10	Correct	21 ms	12320 KB	Output is correct
11	Correct	18 ms	12320 KB	Output is correct
12	Correct	21 ms	12320 KB	Output is correct
13	Correct	18 ms	12320 KB	Output is correct
14	Correct	20 ms	12320 KB	Output is correct
15	Correct	20 ms	12320 KB	Output is correct
16	Correct	21 ms	12320 KB	Output is correct
17	Correct	22 ms	12320 KB	Output is correct
18	Correct	19 ms	12320 KB	Output is correct
19	Correct	21 ms	12320 KB	Output is correct
20	Correct	19 ms	12320 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	12320 KB	Output is correct
2	Correct	18 ms	12320 KB	Output is correct
3	Correct	19 ms	12320 KB	Output is correct
4	Correct	19 ms	12320 KB	Output is correct
5	Correct	21 ms	12320 KB	Output is correct
6	Correct	21 ms	12320 KB	Output is correct
7	Correct	18 ms	12320 KB	Output is correct
8	Correct	22 ms	12320 KB	Output is correct
9	Correct	19 ms	12320 KB	Output is correct
10	Correct	21 ms	12320 KB	Output is correct
11	Correct	20 ms	12320 KB	Output is correct
12	Correct	17 ms	12320 KB	Output is correct
13	Correct	17 ms	12320 KB	Output is correct
14	Correct	18 ms	12320 KB	Output is correct
15	Correct	20 ms	12320 KB	Output is correct
16	Correct	20 ms	12320 KB	Output is correct
17	Correct	21 ms	12320 KB	Output is correct
18	Correct	16 ms	12320 KB	Output is correct
19	Correct	18 ms	12320 KB	Output is correct
20	Correct	20 ms	12320 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	12320 KB	Output is correct
2	Correct	21 ms	12320 KB	Output is correct
3	Correct	22 ms	12320 KB	Output is correct
4	Correct	20 ms	12320 KB	Output is correct
5	Correct	19 ms	12320 KB	Output is correct
6	Correct	21 ms	12320 KB	Output is correct
7	Correct	20 ms	12320 KB	Output is correct
8	Correct	23 ms	12320 KB	Output is correct
9	Correct	24 ms	12320 KB	Output is correct
10	Correct	23 ms	12320 KB	Output is correct
11	Correct	20 ms	12320 KB	Output is correct
12	Correct	19 ms	12320 KB	Output is correct
13	Correct	19 ms	12320 KB	Output is correct
14	Correct	20 ms	12320 KB	Output is correct
15	Correct	17 ms	12320 KB	Output is correct
16	Correct	16 ms	12320 KB	Output is correct
17	Correct	19 ms	12320 KB	Output is correct
18	Correct	20 ms	12320 KB	Output is correct
19	Correct	20 ms	12320 KB	Output is correct
20	Correct	20 ms	12320 KB	Output is correct
21	Correct	22 ms	12320 KB	Output is correct
22	Correct	21 ms	12320 KB	Output is correct
23	Correct	21 ms	12320 KB	Output is correct
24	Correct	22 ms	12320 KB	Output is correct
25	Correct	20 ms	12320 KB	Output is correct

Subtask #4
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	13128 KB	Output is correct
2	Correct	56 ms	13200 KB	Output is correct
3	Correct	62 ms	13208 KB	Output is correct
4	Correct	49 ms	13128 KB	Output is correct
5	Correct	60 ms	13232 KB	Output is correct
6	Correct	48 ms	13136 KB	Output is correct
7	Correct	47 ms	12824 KB	Output is correct
8	Correct	43 ms	12824 KB	Output is correct
9	Correct	47 ms	12828 KB	Output is correct
10	Correct	44 ms	13112 KB	Output is correct
11	Correct	52 ms	13184 KB	Output is correct
12	Correct	55 ms	13224 KB	Output is correct
13	Correct	49 ms	13120 KB	Output is correct
14	Correct	57 ms	13200 KB	Output is correct
15	Correct	55 ms	13192 KB	Output is correct
16	Correct	57 ms	13224 KB	Output is correct
17	Correct	55 ms	13168 KB	Output is correct
18	Correct	45 ms	13088 KB	Output is correct
19	Correct	44 ms	12820 KB	Output is correct
20	Correct	57 ms	13224 KB	Output is correct
21	Correct	53 ms	13232 KB	Output is correct
22	Correct	60 ms	13232 KB	Output is correct
23	Correct	59 ms	13232 KB	Output is correct
24	Correct	61 ms	13232 KB	Output is correct
25	Correct	58 ms	13232 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	13232 KB	Output is correct
2	Correct	58 ms	13232 KB	Output is correct
3	Correct	61 ms	13232 KB	Output is correct
4	Correct	61 ms	13232 KB	Output is correct
5	Correct	60 ms	13224 KB	Output is correct
6	Correct	61 ms	13224 KB	Output is correct
7	Correct	41 ms	12792 KB	Output is correct
8	Correct	32 ms	12772 KB	Output is correct
9	Correct	47 ms	13104 KB	Output is correct
10	Correct	54 ms	13192 KB	Output is correct
11	Correct	47 ms	13112 KB	Output is correct
12	Correct	50 ms	13120 KB	Output is correct
13	Correct	46 ms	12820 KB	Output is correct
14	Correct	53 ms	13176 KB	Output is correct
15	Correct	37 ms	12784 KB	Output is correct
16	Correct	52 ms	13168 KB	Output is correct
17	Correct	47 ms	12828 KB	Output is correct
18	Correct	45 ms	13088 KB	Output is correct
19	Correct	51 ms	13200 KB	Output is correct
20	Correct	45 ms	13088 KB	Output is correct
21	Correct	57 ms	13232 KB	Output is correct
22	Correct	62 ms	13232 KB	Output is correct
23	Correct	60 ms	13228 KB	Output is correct
24	Correct	58 ms	13224 KB	Output is correct
25	Correct	61 ms	13228 KB	Output is correct

Submission #2260

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 15.0 / 15.0

Subtask #3 20.0 / 20.0

Subtask #4 25.0 / 25.0

Subtask #5 30.0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
15.0 / 15.0

Subtask #3
20.0 / 20.0

Subtask #4
25.0 / 25.0

Subtask #5
30.0 / 30.0