답안 #5225 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5225	2014-02-18T07:46:59 Z	ainta	생일수 II (GA4_birthday2)	C++	100 / 100	116 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	40 ms	10656 KB	Output is correct
2	Correct	32 ms	10656 KB	Output is correct
3	Correct	28 ms	10656 KB	Output is correct
4	Correct	28 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	36 ms	10656 KB	Output is correct
8	Correct	40 ms	10656 KB	Output is correct
9	Correct	36 ms	10656 KB	Output is correct
10	Correct	32 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	28 ms	10656 KB	Output is correct
14	Correct	40 ms	10656 KB	Output is correct
15	Correct	32 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	36 ms	10656 KB	Output is correct
19	Correct	40 ms	10656 KB	Output is correct
20	Correct	44 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	36 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	40 ms	10656 KB	Output is correct
6	Correct	40 ms	10656 KB	Output is correct
7	Correct	40 ms	10656 KB	Output is correct
8	Correct	40 ms	10656 KB	Output is correct
9	Correct	40 ms	10656 KB	Output is correct
10	Correct	32 ms	10656 KB	Output is correct
11	Correct	40 ms	10656 KB	Output is correct
12	Correct	36 ms	10656 KB	Output is correct
13	Correct	36 ms	10656 KB	Output is correct
14	Correct	40 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	40 ms	10656 KB	Output is correct
18	Correct	40 ms	10656 KB	Output is correct
19	Correct	44 ms	10656 KB	Output is correct
20	Correct	40 ms	10656 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	10656 KB	Output is correct
2	Correct	36 ms	10656 KB	Output is correct
3	Correct	44 ms	10656 KB	Output is correct
4	Correct	40 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	40 ms	10656 KB	Output is correct
8	Correct	32 ms	10656 KB	Output is correct
9	Correct	40 ms	10656 KB	Output is correct
10	Correct	40 ms	10656 KB	Output is correct
11	Correct	40 ms	10656 KB	Output is correct
12	Correct	44 ms	10656 KB	Output is correct
13	Correct	44 ms	10656 KB	Output is correct
14	Correct	40 ms	10656 KB	Output is correct
15	Correct	40 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	36 ms	10656 KB	Output is correct
19	Correct	40 ms	10656 KB	Output is correct
20	Correct	44 ms	10656 KB	Output is correct

Subtask #4
25.0 / 25.0

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

Subtask #5
30.0 / 30.0

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

답안 #5225

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