답안 #2540 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2540	2013-07-23T07:31:09 Z	tncks0121	생일수 II (GA4_birthday2)	C++	100 / 100	85 ms	6168 KB

birthday2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>

using namespace std;
typedef long long ll;
const int INF = 987654321;
const ll LINF = (ll)1e15;

const int N = 200000;
const int N_ = N+10;
const ll MOD = 19980305;

struct mint {
    int v;
    mint(): v(0) { }
    mint(ll v): v((v+MOD*1000)%MOD) { }
    
    int operator*(){ return v; }
    
    mint operator+ (ll t) { return mint(v + t); }
    mint operator- (ll t) { return mint(v - t); }
    mint operator* (ll t) { return mint(v * t); }
    mint operator+ (mint t) { return mint(v + t.v); }
    mint operator- (mint t) { return mint(v - t.v); }
    mint operator* (mint t) { return mint((ll)v * t.v); }
};

mint operator+ (ll a, mint t) { return mint(a + t.v); }
mint operator- (ll a, mint t) { return mint(a - t.v); }
mint operator* (ll a, mint t) { return mint(a * t.v); }

mint E[N_];
mint A[N_], B[N_];
mint P3[N_], P10[N_];
mint T[N_];
char X[N_], Y[N_];

mint f (mint P, int n) {
    P = P * P10[n];
    mint ret = P3[n] - 1;
    ret = ret * P + B[n];
    ret = ret * P + T[n];
    return ret;
}

mint get (char *V) {
    int L = 0;
    mint ret, last, prefix;
    
    while(V[++L]); --L;
    
    for(int i = 1; i < L; i++) {
        ret = ret + last * (3 * E[i]) + T[i];
        last = 8 * E[i];
    }
    
    for(int i = 1; i <= L; i++) {
        if(V[i] >= '5') {
            mint low_prefix = prefix * 10 + 3;
            mint first = low_prefix * P10[L - i] + 3 * E[L - i];
            ret = ret + last * first + f(low_prefix, L - i);
            last = low_prefix * P10[L - i] + 8 * E[L - i];
        }
        if(V[i] >= '8') {
            mint low_prefix = prefix * 10 + 5;
            mint first = low_prefix * P10[L - i] + 3 * E[L - i];
            ret = ret + last * first + f(low_prefix, L - i);
            last = low_prefix * P10[L - i] + 8 * E[L - i];
        }
        prefix = prefix * 10 + (V[i] - '0');
    }
    
    ret = ret + last * prefix;
    return ret;
}

int main (){
    int i, j;
    
    P3[0] = P10[0] = 1;
    for(i = 1; i <= N; i++) {
        E[i] = E[i - 1] * 10 + 1;
        P3[i] = P3[i - 1] * 3;
        P10[i] = P10[i - 1] * 10;
        A[i] = A[i - 1] * 30 + 16 * P3[i - 1];
        B[i] = 2 * A[i] - 11 * E[i];
        T[i] = f(3, i - 1)
               + (3 * P10[i - 1] + 8 * E[i - 1]) * (5 * P10[i - 1] + 3 * E[i - 1]) + f(5, i - 1)
               + (5 * P10[i - 1] + 8 * E[i - 1]) * (8 * P10[i - 1] + 3 * E[i - 1]) + f(8, i - 1);
    }
    
    scanf("%s%s", X+1, Y+1);
    
    printf("%d\n", *(get(Y) - get(X)));
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	6168 KB	Output is correct
2	Correct	32 ms	6168 KB	Output is correct
3	Correct	36 ms	6168 KB	Output is correct
4	Correct	36 ms	6168 KB	Output is correct
5	Correct	36 ms	6168 KB	Output is correct
6	Correct	36 ms	6168 KB	Output is correct
7	Correct	32 ms	6168 KB	Output is correct
8	Correct	36 ms	6168 KB	Output is correct
9	Correct	36 ms	6168 KB	Output is correct
10	Correct	36 ms	6168 KB	Output is correct
11	Correct	36 ms	6168 KB	Output is correct
12	Correct	36 ms	6168 KB	Output is correct
13	Correct	36 ms	6168 KB	Output is correct
14	Correct	36 ms	6168 KB	Output is correct
15	Correct	36 ms	6168 KB	Output is correct
16	Correct	32 ms	6168 KB	Output is correct
17	Correct	36 ms	6168 KB	Output is correct
18	Correct	36 ms	6168 KB	Output is correct
19	Correct	32 ms	6168 KB	Output is correct
20	Correct	32 ms	6168 KB	Output is correct
21	Correct	41 ms	5968 KB	Output is correct
22	Correct	40 ms	5968 KB	Output is correct
23	Correct	41 ms	5968 KB	Output is correct
24	Correct	41 ms	5968 KB	Output is correct
25	Correct	41 ms	5968 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	6168 KB	Output is correct
2	Correct	68 ms	6168 KB	Output is correct
3	Correct	72 ms	6168 KB	Output is correct
4	Correct	68 ms	6168 KB	Output is correct
5	Correct	72 ms	6168 KB	Output is correct
6	Correct	72 ms	6168 KB	Output is correct
7	Correct	72 ms	6168 KB	Output is correct
8	Correct	72 ms	6168 KB	Output is correct
9	Correct	68 ms	6168 KB	Output is correct
10	Correct	72 ms	6168 KB	Output is correct
11	Correct	64 ms	6168 KB	Output is correct
12	Correct	72 ms	6168 KB	Output is correct
13	Correct	68 ms	6168 KB	Output is correct
14	Correct	68 ms	6168 KB	Output is correct
15	Correct	72 ms	6168 KB	Output is correct
16	Correct	72 ms	6168 KB	Output is correct
17	Correct	72 ms	6168 KB	Output is correct
18	Correct	72 ms	6168 KB	Output is correct
19	Correct	72 ms	6168 KB	Output is correct
20	Correct	68 ms	6168 KB	Output is correct
21	Correct	83 ms	5968 KB	Output is correct
22	Correct	85 ms	5968 KB	Output is correct
23	Correct	83 ms	5968 KB	Output is correct
24	Correct	84 ms	5968 KB	Output is correct
25	Correct	82 ms	5968 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	6168 KB	Output is correct
2	Correct	72 ms	6168 KB	Output is correct
3	Correct	72 ms	6168 KB	Output is correct
4	Correct	68 ms	6168 KB	Output is correct
5	Correct	64 ms	6168 KB	Output is correct
6	Correct	72 ms	6168 KB	Output is correct
7	Correct	72 ms	6168 KB	Output is correct
8	Correct	72 ms	6168 KB	Output is correct
9	Correct	68 ms	6168 KB	Output is correct
10	Correct	68 ms	6168 KB	Output is correct
11	Correct	68 ms	6168 KB	Output is correct
12	Correct	72 ms	6168 KB	Output is correct
13	Correct	72 ms	6168 KB	Output is correct
14	Correct	72 ms	6168 KB	Output is correct
15	Correct	72 ms	6168 KB	Output is correct
16	Correct	52 ms	6168 KB	Output is correct
17	Correct	52 ms	6168 KB	Output is correct
18	Correct	52 ms	6168 KB	Output is correct
19	Correct	52 ms	6168 KB	Output is correct
20	Correct	52 ms	6168 KB	Output is correct
21	Correct	83 ms	5968 KB	Output is correct
22	Correct	80 ms	5968 KB	Output is correct
23	Correct	82 ms	5968 KB	Output is correct
24	Correct	81 ms	5968 KB	Output is correct
25	Correct	83 ms	5968 KB	Output is correct

답안 #2540

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