This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |