提出 #5945816

---

ソースコード 拡げる

#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;
}

提出情報

ジャッジ結果