AtCoder Regular Contest 020 C - A mod B Problem

問題

　ある整数を与えるのでをで割った余りを求めなさい。しかしは非常に大きく、についてが回繰り返されたものを上の桁から順番に並べたものとして表されるものとする。

解法

　ダブリング。を回並べてできる整数をとすると、を回並べてできる整数は$$ k \times (10^{aの桁数 \times 2^n} + 1)$$である。これは123を2回並べた123123から4回並べた123123123123を作る過程など具体例を考えるとわかりやすい。

　このようにすれば各についてを回並べてできる整数は小さいほうから順番に求めていくことができるので、をの累乗の和として表現しなおせば上で求めたもののみを使ってを回並べた整数の余りを求めることができる。

　各について余りが求まれば、それを順番に桁数分シフトながら余りとして足していけば最終的な答えが得られる。

反省

　2時間6分(3WA)でAC。1時間ほど考えて20点分の解答しかわからなかったので解答を見てまず99点分の解答を書いて、そのあと満点解法を書いた。解法が難しいのもそうだけど桁をずらしながら足していく操作も慣れていなくて実装が大変だった。

　手元のメモを見返すと思いっきり等比数列っぽいものは書いているのに99点解法が思い浮かばなかったのは良くない。しかし結局桁をずらしながら足していけば求まるというコア部分が見えていないのでこういう発想に至らなかったともいえるので、これは慣れによって何とかなる気もする。

　ダブリングは必須テクニックなので敏感になっていきたい。どういうときに思い浮かべばいいのかまだよくわかっていないけど、同じ操作を大きな数やる場合などか。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll B;

ll POW(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m & 1) {
            result *= n;
            result %= B;
        }

        m /= 2;
        n *= n;
        n %= B;
    }
    return result;
}

ll MOD(ll a, ll L) {
    //a[i]の桁数
    const ll d = to_string(a).size();

    //aがpow(2, i)回繰り返されたものの余りをf[i]に格納していく
    vector<ll> f;
    f.push_back(a);
    for (ll i = 1; pow(2, i) <= L; i++) {
        f.push_back(f[i - 1] * ((POW(10, pow(2, i - 1) * d) + 1) % B) % B);
    }

    ll result = 0;
    ll curr_d = 0;
    for (ll i = 0; pow(2, i) <= L; i++) {
        if (L & (1 << i)) {
            //ビットが立っていたら足す
            result += f[i] * POW(10, curr_d) % B;
            result %= B;

            //桁を更新
            curr_d += d * pow(2, i);
        }
    }

    return result;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N), L(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i] >> L[i];
    }
    cin >> B;

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        //a[i]の桁数
        const ll d = to_string(a[i]).size();

        ll m = MOD(a[i], L[i]);

        //前回までの余りを今回の桁数分シフトして今回の余りと足す
        ans = (ans * POW(10, d * L[i]) % B + m) % B;
    }

    cout << ans << endl;
}