답안 #5224 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5224	2014-02-18T07:46:40 Z	ainta	생일수 II (GA4_birthday2)	C++	100 / 100	128 ms	10656 KB

birthday2

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N_ 200010
long long po[N_ * 2], D1[N_], S[N_], po2[N_], D2[N_], Mod=19980305, Res, R1;
char p[N_];
void Do(long long Sum, int Len){
	Res = (Res + D2[Len] + Sum * Sum % Mod * (po2[Len] - 1) % Mod + (Sum * S[Len] * 2) % Mod - Sum * D1[Len] * (8 + 3) % Mod + Mod) % Mod;
}
void Gap(){
	int i, n = strlen(p);
	Res = 0;
	long long Sum = 0, tp;
	for (i = 1; i < n; i++){
		Res = (Res + D2[i] + D1[i] * D1[i+1] * 24) % Mod;
	}
	for (i = 0; i < n; i++){
		Sum = (Sum + po[n - i - 1] * 3) % Mod;
		if (p[i] == '3')continue;
		Do(Sum, n - i - 1);
		Res = (Res + Sum * 3 * D1[n - i - 1]) % Mod;
		tp = (Sum + po[n - i - 1] * 2) % Mod;
		Res = (Res + tp * 8 * D1[n - i - 1] + Sum * tp % Mod + D1[n - i - 1] * D1[n - i - 1] * 24) % Mod;
		Sum = tp;
		if (p[i] == '5')continue;
		Do(Sum, n - i - 1);
		Res = (Res + Sum * 3 * D1[n - i - 1]) % Mod;
		tp = (Sum + po[n - i - 1] * 3) % Mod;
		Res = (Res + tp * 8 * D1[n - i - 1] + Sum * tp % Mod + D1[n - i - 1] * D1[n - i - 1] * 24) % Mod;
		Sum = tp;
	}
}
int main()
{
	int i, t = 0;
	po[0] = po2[0] = 1;
	for (i = 1; i < N_ * 2; i++)po[i] = po[i - 1] * 10 % Mod;
	for (i = 1; i < N_; i++)po2[i] = po2[i - 1] * 3 % Mod;
	for (i = 1; i < N_; i++)D1[i] = (D1[i - 1] + po[i - 1]) % Mod;
	for (i = 1; i < N_; i++)S[i] = (S[i - 1] * 3 + po2[i - 1] * (3 + 5 + 8)*po[i - 1]) % Mod;
	for (i = 1; i < N_; i++)D2[i] = (D2[i - 1] * 3 + ((3 + 5 + 8)*po[i - 1] * S[i - 1] * 2) % Mod - (D1[i - 1] * po[i - 1] * 48) % Mod + ((3 * 3 + 5 * 5 + 8 * 8)*(po2[i - 1] - 1) + 3 * 5 + 5 * 8) % Mod*po[2 * i - 2] % Mod + 2 * D1[i - 1] * D1[i - 1] * 8 * 3 % Mod + Mod) % Mod;	
	scanf("%s", p);
	Gap();
	R1 = Res;
	scanf("%s", p);
	Gap();
	printf("%lld\n", (Res - R1 + Mod) % Mod);
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	10656 KB	Output is correct
2	Correct	40 ms	10656 KB	Output is correct
3	Correct	40 ms	10656 KB	Output is correct
4	Correct	44 ms	10656 KB	Output is correct
5	Correct	40 ms	10656 KB	Output is correct
6	Correct	40 ms	10656 KB	Output is correct
7	Correct	44 ms	10656 KB	Output is correct
8	Correct	36 ms	10656 KB	Output is correct
9	Correct	32 ms	10656 KB	Output is correct
10	Correct	40 ms	10656 KB	Output is correct
11	Correct	28 ms	10656 KB	Output is correct
12	Correct	40 ms	10656 KB	Output is correct
13	Correct	36 ms	10656 KB	Output is correct
14	Correct	36 ms	10656 KB	Output is correct
15	Correct	36 ms	10656 KB	Output is correct
16	Correct	44 ms	10656 KB	Output is correct
17	Correct	36 ms	10656 KB	Output is correct
18	Correct	40 ms	10656 KB	Output is correct
19	Correct	28 ms	10656 KB	Output is correct
20	Correct	40 ms	10656 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	10656 KB	Output is correct
2	Correct	40 ms	10656 KB	Output is correct
3	Correct	36 ms	10656 KB	Output is correct
4	Correct	36 ms	10656 KB	Output is correct
5	Correct	44 ms	10656 KB	Output is correct
6	Correct	40 ms	10656 KB	Output is correct
7	Correct	28 ms	10656 KB	Output is correct
8	Correct	44 ms	10656 KB	Output is correct
9	Correct	40 ms	10656 KB	Output is correct
10	Correct	36 ms	10656 KB	Output is correct
11	Correct	40 ms	10656 KB	Output is correct
12	Correct	40 ms	10656 KB	Output is correct
13	Correct	32 ms	10656 KB	Output is correct
14	Correct	36 ms	10656 KB	Output is correct
15	Correct	44 ms	10656 KB	Output is correct
16	Correct	40 ms	10656 KB	Output is correct
17	Correct	36 ms	10656 KB	Output is correct
18	Correct	40 ms	10656 KB	Output is correct
19	Correct	36 ms	10656 KB	Output is correct
20	Correct	36 ms	10656 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	10656 KB	Output is correct
2	Correct	40 ms	10656 KB	Output is correct
3	Correct	36 ms	10656 KB	Output is correct
4	Correct	44 ms	10656 KB	Output is correct
5	Correct	36 ms	10656 KB	Output is correct
6	Correct	56 ms	10656 KB	Output is correct
7	Correct	36 ms	10656 KB	Output is correct
8	Correct	48 ms	10656 KB	Output is correct
9	Correct	44 ms	10656 KB	Output is correct
10	Correct	36 ms	10656 KB	Output is correct
11	Correct	36 ms	10656 KB	Output is correct
12	Correct	36 ms	10656 KB	Output is correct
13	Correct	56 ms	10656 KB	Output is correct
14	Correct	44 ms	10656 KB	Output is correct
15	Correct	48 ms	10656 KB	Output is correct
16	Correct	40 ms	10656 KB	Output is correct
17	Correct	44 ms	10656 KB	Output is correct
18	Correct	36 ms	10656 KB	Output is correct
19	Correct	40 ms	10656 KB	Output is correct
20	Correct	48 ms	10656 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	108 ms	10656 KB	Output is correct
2	Correct	112 ms	10656 KB	Output is correct
3	Correct	128 ms	10656 KB	Output is correct
4	Correct	108 ms	10656 KB	Output is correct
5	Correct	104 ms	10656 KB	Output is correct
6	Correct	108 ms	10656 KB	Output is correct
7	Correct	108 ms	10656 KB	Output is correct
8	Correct	108 ms	10656 KB	Output is correct
9	Correct	112 ms	10656 KB	Output is correct
10	Correct	112 ms	10656 KB	Output is correct
11	Correct	108 ms	10656 KB	Output is correct
12	Correct	116 ms	10656 KB	Output is correct
13	Correct	120 ms	10656 KB	Output is correct
14	Correct	108 ms	10656 KB	Output is correct
15	Correct	112 ms	10656 KB	Output is correct
16	Correct	120 ms	10656 KB	Output is correct
17	Correct	128 ms	10656 KB	Output is correct
18	Correct	104 ms	10656 KB	Output is correct
19	Correct	116 ms	10656 KB	Output is correct
20	Correct	128 ms	10656 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	108 ms	10656 KB	Output is correct
2	Correct	116 ms	10656 KB	Output is correct
3	Correct	116 ms	10656 KB	Output is correct
4	Correct	120 ms	10656 KB	Output is correct
5	Correct	120 ms	10656 KB	Output is correct
6	Correct	120 ms	10656 KB	Output is correct
7	Correct	116 ms	10656 KB	Output is correct
8	Correct	120 ms	10656 KB	Output is correct
9	Correct	116 ms	10656 KB	Output is correct
10	Correct	116 ms	10656 KB	Output is correct
11	Correct	116 ms	10656 KB	Output is correct
12	Correct	116 ms	10656 KB	Output is correct
13	Correct	112 ms	10656 KB	Output is correct
14	Correct	116 ms	10656 KB	Output is correct
15	Correct	112 ms	10656 KB	Output is correct
16	Correct	80 ms	10656 KB	Output is correct
17	Correct	68 ms	10656 KB	Output is correct
18	Correct	72 ms	10656 KB	Output is correct
19	Correct	80 ms	10656 KB	Output is correct
20	Correct	84 ms	10656 KB	Output is correct

답안 #5224

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