답안 #1498 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1498	2013-07-06T01:35:02 Z	tncks0121	생일수 II (GA4_birthday2)	C++	100 / 100	104 ms	5968 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	40 ms	5968 KB	Output is correct
2	Correct	47 ms	5968 KB	Output is correct
3	Correct	41 ms	5968 KB	Output is correct
4	Correct	44 ms	5968 KB	Output is correct
5	Correct	41 ms	5968 KB	Output is correct
6	Correct	41 ms	5968 KB	Output is correct
7	Correct	41 ms	5968 KB	Output is correct
8	Correct	42 ms	5968 KB	Output is correct
9	Correct	40 ms	5968 KB	Output is correct
10	Correct	41 ms	5968 KB	Output is correct
11	Correct	40 ms	5968 KB	Output is correct
12	Correct	41 ms	5968 KB	Output is correct
13	Correct	41 ms	5968 KB	Output is correct
14	Correct	43 ms	5968 KB	Output is correct
15	Correct	43 ms	5968 KB	Output is correct
16	Correct	39 ms	5968 KB	Output is correct
17	Correct	41 ms	5968 KB	Output is correct
18	Correct	40 ms	5968 KB	Output is correct
19	Correct	50 ms	5968 KB	Output is correct
20	Correct	41 ms	5968 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	5968 KB	Output is correct
2	Correct	39 ms	5968 KB	Output is correct
3	Correct	50 ms	5968 KB	Output is correct
4	Correct	49 ms	5968 KB	Output is correct
5	Correct	47 ms	5968 KB	Output is correct
6	Correct	41 ms	5968 KB	Output is correct
7	Correct	49 ms	5968 KB	Output is correct
8	Correct	49 ms	5968 KB	Output is correct
9	Correct	47 ms	5968 KB	Output is correct
10	Correct	51 ms	5968 KB	Output is correct
11	Correct	42 ms	5968 KB	Output is correct
12	Correct	47 ms	5968 KB	Output is correct
13	Correct	40 ms	5968 KB	Output is correct
14	Correct	40 ms	5968 KB	Output is correct
15	Correct	41 ms	5968 KB	Output is correct
16	Correct	48 ms	5968 KB	Output is correct
17	Correct	42 ms	5968 KB	Output is correct
18	Correct	46 ms	5968 KB	Output is correct
19	Correct	42 ms	5968 KB	Output is correct
20	Correct	39 ms	5968 KB	Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	5968 KB	Output is correct
2	Correct	97 ms	5968 KB	Output is correct
3	Correct	79 ms	5968 KB	Output is correct
4	Correct	86 ms	5968 KB	Output is correct
5	Correct	97 ms	5968 KB	Output is correct
6	Correct	84 ms	5968 KB	Output is correct
7	Correct	69 ms	5968 KB	Output is correct
8	Correct	80 ms	5968 KB	Output is correct
9	Correct	80 ms	5968 KB	Output is correct
10	Correct	82 ms	5968 KB	Output is correct
11	Correct	92 ms	5968 KB	Output is correct
12	Correct	93 ms	5968 KB	Output is correct
13	Correct	84 ms	5968 KB	Output is correct
14	Correct	96 ms	5968 KB	Output is correct
15	Correct	91 ms	5968 KB	Output is correct
16	Correct	97 ms	5968 KB	Output is correct
17	Correct	86 ms	5968 KB	Output is correct
18	Correct	80 ms	5968 KB	Output is correct
19	Correct	66 ms	5968 KB	Output is correct
20	Correct	98 ms	5968 KB	Output is correct
21	Correct	82 ms	5968 KB	Output is correct
22	Correct	98 ms	5968 KB	Output is correct
23	Correct	104 ms	5968 KB	Output is correct
24	Correct	100 ms	5968 KB	Output is correct
25	Correct	103 ms	5968 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	100 ms	5968 KB	Output is correct
2	Correct	82 ms	5968 KB	Output is correct
3	Correct	98 ms	5968 KB	Output is correct
4	Correct	83 ms	5968 KB	Output is correct
5	Correct	102 ms	5968 KB	Output is correct
6	Correct	80 ms	5968 KB	Output is correct
7	Correct	59 ms	5968 KB	Output is correct
8	Correct	55 ms	5968 KB	Output is correct
9	Correct	69 ms	5968 KB	Output is correct
10	Correct	91 ms	5968 KB	Output is correct
11	Correct	68 ms	5968 KB	Output is correct
12	Correct	84 ms	5968 KB	Output is correct
13	Correct	79 ms	5968 KB	Output is correct
14	Correct	90 ms	5968 KB	Output is correct
15	Correct	69 ms	5968 KB	Output is correct
16	Correct	90 ms	5968 KB	Output is correct
17	Correct	78 ms	5968 KB	Output is correct
18	Correct	82 ms	5968 KB	Output is correct
19	Correct	93 ms	5968 KB	Output is correct
20	Correct	81 ms	5968 KB	Output is correct
21	Correct	82 ms	5968 KB	Output is correct
22	Correct	81 ms	5968 KB	Output is correct
23	Correct	96 ms	5968 KB	Output is correct
24	Correct	96 ms	5968 KB	Output is correct
25	Correct	94 ms	5968 KB	Output is correct

답안 #1498

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