提出 #73941070

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

const int BASE = 10007;

int add(int x, int y) {
    x += y;
    if (x >= BASE) return x-BASE;
    return x;
}
int sub(int x, int y) {
    x -= y;
    if (x < 0) return x+BASE;
    return x;
}
int mult(int x, int y, int base=BASE) {
    return (long long) x * y % base;
}
int bin_pow(int x, int y, int base=BASE) {
    int res = 1;
    while (y) {
        if (y & 1) res = mult(res, x, base);
        y >>= 1;
        x = mult(x, x, base);
    }
    return res;
}
int inverse(int x) {
    return bin_pow(x, BASE-2);
}

int main() {
    int k, m;
    cin >> k >> m; // note: m < BASE
    vector<int> c(k), l(k);
    for (int i = 0; i < k; ++i) cin >> c[i] >> l[i];

    // precompute per digit
    vector<int> digMod[10], digWhole[10];
    int digFirst[10], digPeriod[10];
    vector<int> digWholeMult[10], digWholeNew[10];

    auto update = [&](int mod, int whole, int nextDigit) {
        int v = mod * 10 + nextDigit;
        int md = v % m;
        int wh = (v / m + whole*10) % BASE;
        return pair<int, int>{md, wh};
    };

    for (int d = 1; d <= 9; ++d) {
        vector<int> mod, whole;
        map<int, int> seenMod;
        mod.push_back(0), whole.push_back(0);
        seenMod[0] = 0;
        int first = -1, period = -1;
        while (true) {
            auto [md, wh] = update(mod.back(), whole.back(), d);
            mod.push_back(md), whole.push_back(wh);
            if (seenMod.count(md)) {
                first = seenMod[md];
                period = (int)mod.size()-1 - first;
                break;
            }
            seenMod[md] = (int)mod.size() - 1;
        }

        vector<int> wholeMult(1+period), wholeNew(1+period);
        wholeMult[0] = 1, wholeNew[0] = 0;
        int curMod = mod[first];
        for (int i = 1; i <= period; ++i) {
            wholeMult[i] = (wholeMult[i-1] * 10) % BASE; // pow10 mod BASE
            tie(curMod, wholeNew[i]) = update(curMod, wholeNew[i-1], d);
        }
        assert(curMod == mod[first]);

        digMod[d] = mod, digWhole[d] = whole;
        digFirst[d] = first, digPeriod[d] = period;
        digWholeMult[d] = wholeMult, digWholeNew[d] = wholeNew;
    }

    int total = 0, rem = 0;
    long long trailingZeros = 0;
    for (int i = k-1; i >= 0; --i) {
        if (c[i] != 0) {
            int md = digMod[c[i]][min(l[i], digFirst[c[i]])];
            int wh = digWhole[c[i]][min(l[i], digFirst[c[i]])];
            int remL = max(l[i] - digFirst[c[i]], 0);
            int jumps = remL / digPeriod[c[i]], extra = remL % digPeriod[c[i]];
            
            auto apply = [&](int pos, int cnt) { // modifies md and wh
                // * c1 + c2 repeated cnt times
                int c1 = digWholeMult[c[i]][pos], c2 = digWholeNew[c[i]][pos];
                
                if (c1 == 1) {
                    wh = add(wh, mult(c2, cnt));
                } else {
                    int c3 = mult(c2, inverse(c1-1));
                    // same as add c3, multiply by c1 cnt times, then subtract c3
                    wh = add(wh, c3);
                    wh = mult(wh, bin_pow(c1, cnt % (BASE-1)));
                    wh = sub(wh, c3);
                }
            };

            apply(digPeriod[c[i]], jumps);
            apply(extra, 1);
            md = digMod[c[i]][digFirst[c[i]] + extra];

            // now consider trailing zeros
            auto combine = [&](int w1, int mtw1, int m1, int w2, int mtw2, int m2) {
                int w = w1 * w2 % BASE;
                int mtw = (mtw1 * w2 + m1 * mtw2 + (m1*m2/m)) % BASE;
                int mm = m1 * m2 % m;
                return tuple<int, int, int>{w, mtw, mm};
            };
            long long pow10 = trailingZeros;
            int wholeMult = 1, modToWhole = 0, modMult = 1;
            int wMult = 10 % BASE, mtw = (10/m)%BASE, mMult = 10 % m;
            while (pow10) {
                if (pow10 & 1) {
                    tie(wholeMult, modToWhole, modMult) = combine(wholeMult, modToWhole, modMult, wMult, mtw, mMult);
                }
                pow10 >>= 1;
                tie(wMult, mtw, mMult) = combine(wMult, mtw, mMult, wMult, mtw, mMult);
            }

            wh = ((long long)wh * wholeMult + (long long)modToWhole * md) % BASE;
            wh = (wh + (long long)modMult * md / m) % BASE;
            md = (long long)modMult * md % m;

            total = (total + wh) % BASE;
            rem = rem + md;
            total += rem / m;
            rem %= m;
            total %= BASE;
        }
        trailingZeros += l[i];
    }
    cout << total << endl;
    return 0;
}

提出情報

ジャッジ結果