Submission #5945816


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

ll L, A, B, MOD, ten;

struct mll {
    ll x;
    mll(ll x=0): x(x%MOD){
    }
    mll& operator+=(const mll a) {
        (x += a.x) %= MOD;
        return *this;
    }
    mll& operator-=(const mll a) {
        (x += MOD-a.x) %= MOD;
        return *this;
    }
    mll& operator*=(const mll a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mll operator+(const mll a) const {
        mll res(*this);
        return res+=a;
    }
    mll operator-(const mll a) const {
        mll res(*this);
        return res-=a;
    }
    mll operator*(const mll a) const {
        mll res(*this);
        return res*=a;
    }
};

// x^y
mll pow_(mll x, ll y) {
    if (y==0)
        return mll(1);
    else if(y%2==1) {
        return pow_(x, y-1) * x;
    } else {
        mll z = pow_(x, y/2);
        return z*z;
    }
}

mll f(ll l) {
    if (l==0)
        return 0;

    if (l%2==1){
        ll pl = l-1;
        mll x = f(pl);
        return x*mll(ten)*mll(10)+mll(1);
    } else {
        ll pl = l/2;
        mll x = f(pl);
        return x*pow_(mll(ten)*mll(10), pl) + x;
    }
    return 0;
}

mll g(ll l) {
    if (l==0)
        return 0;

    if (l%2==1) {
        ll pl = l-1;
        mll x = g(pl);
        return x*mll(ten)*mll(10) + B*pl;
    } else {
        ll pl = l/2;
        mll x = g(pl);
        return x*pow_(mll(ten)*mll(10), pl) + x + mll(B)*mll(pl)*f(pl);
    }
}

signed main() {
    cin>>L>>A>>B>>MOD;
    mll ans(0);

    ten = 1;
    for (ll k=0; k<18; k++, ten*=10) { // [ 10^k  10^(k+1) ) の区間について
        if (A+B*(L-1) < ten) continue;
        if (10*ten <= A) continue;
        ll a; // 区間内での初項
        if (ten <= A) {
            a = A;
        } else{
            a = (ten-A + B-1)/B * B + A;
        }
        ll last; // 区間内での最後の項
        if (A+B*(L-1) < 10*ten) {
            last = A+B*(L-1);
        } else {
            last = (10*ten-1 - A)/B * B + A;
        }
        ll l = (last-a)/B + 1; // 区間内での項の数

        if (last < a) continue;


        mll ans_k = mll(a)*f(l) + g(l);
        ans *= pow_(mll(10*ten), l);
        ans += ans_k;

        //printf("k=%d [%2lld %2lld) %2lld -> %2lld (%lld) ans_k=%d\n",
        //        k, ten, ten*10, a, last, l, ans_k.x);
    }
    cout<<ans.x<<endl;
    return 0;
}

Submission Info

Submission Time
Task F - Takahashi's Basics in Education and Learning
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2613 Byte
Status
Exec Time 8 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sample_03.txt, sub1_killer_01.txt, sub1_killer_02.txt, sub1_killer_03.txt, sub1_killer_04.txt, sub1_killer_05.txt, sub1_killer_06.txt, sub1_killer_07.txt, sub1_large_01.txt, sub1_large_02.txt, sub1_large_03.txt, sub1_large_04.txt, sub1_large_05.txt, sub1_large_06.txt, sub1_large_07.txt, sub1_large_08.txt, sub1_large_09.txt, sub1_rand_01.txt, sub1_rand_02.txt, sub1_rand_03.txt, sub1_rand_04.txt, sub1_rand_05.txt, sub1_rand_06.txt, sub1_rand_07.txt, sub1_rand_08.txt, sub1_rand_09.txt, sub1_rand_10.txt, sub1_small_01.txt, sub1_small_02.txt, sub1_small_03.txt, sub1_small_04.txt, sub1_small_05.txt, sub1_small_06.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sub1_killer_01.txt 3 ms 256 KB
sub1_killer_02.txt 2 ms 256 KB
sub1_killer_03.txt 7 ms 256 KB
sub1_killer_04.txt 1 ms 256 KB
sub1_killer_05.txt 1 ms 256 KB
sub1_killer_06.txt 2 ms 256 KB
sub1_killer_07.txt 2 ms 256 KB
sub1_large_01.txt 7 ms 256 KB
sub1_large_02.txt 1 ms 256 KB
sub1_large_03.txt 2 ms 256 KB
sub1_large_04.txt 8 ms 256 KB
sub1_large_05.txt 4 ms 256 KB
sub1_large_06.txt 3 ms 256 KB
sub1_large_07.txt 5 ms 256 KB
sub1_large_08.txt 4 ms 256 KB
sub1_large_09.txt 4 ms 256 KB
sub1_rand_01.txt 2 ms 256 KB
sub1_rand_02.txt 2 ms 256 KB
sub1_rand_03.txt 2 ms 256 KB
sub1_rand_04.txt 1 ms 256 KB
sub1_rand_05.txt 1 ms 256 KB
sub1_rand_06.txt 1 ms 256 KB
sub1_rand_07.txt 5 ms 256 KB
sub1_rand_08.txt 2 ms 256 KB
sub1_rand_09.txt 2 ms 256 KB
sub1_rand_10.txt 1 ms 256 KB
sub1_small_01.txt 1 ms 256 KB
sub1_small_02.txt 1 ms 256 KB
sub1_small_03.txt 1 ms 256 KB
sub1_small_04.txt 1 ms 256 KB
sub1_small_05.txt 1 ms 256 KB
sub1_small_06.txt 1 ms 256 KB