ABC129 Fにみるたのしいダブリング

深夜テンション(カラータイルをTLで見かけて3時になってしまったので)

ダブリングとは?

2倍する or 1足す を O(logN)$O(\log N)$ 回繰り返すだけで N$N$ に到達できることを利用したもの全般 半分にする or 1引く を繰り返して N$N$ を 0$0$ とかにする とみるほうが自然かも

例 : 繰り返し二乗法

auto pow = [](auto a, auto n){
    auto ret = 1;
    while(n){
        if(n & 1)ret *= a; // 1引く
        a *= a; // 半分にする
        n >>= 1;
    }
    return ret;
}

ABC129 F

ネタバレです

桁数で場合分けをしたあとを考えましょう(r$r$ 桁)

求めたいものは ∑i=0L−110(L−i−1)r(A+Bi)${\displaystyle \sum _{i=0}^{L-1}{10}^{(L-i-1)r}(A+Bi)}$ です。

ここで、L$L$ を1減らすのと半分にすることを考えます。上の繰り返し二乗法でしたように、最終的(ここではbase caseです 今回は L=0$L=0$ まで等差数列を短くできたとき)に答えの入る変数 ret を作っておきましょう。

すると、L$L$を1減らすのは ret の末尾に A を加えて A += B とすること、半分にすることは Aの末尾にA + Bを加えて、Bを2倍して自身を末尾に加えることになります(L$L$ を半分にするとは、等差数列を2項ずつまとめて見ることと等しいので)。

このように考えると、自然にダブリングでABC129 Fを解くことができます。

以下のコードで、R=10r$R={10}^r$ です。

ret = 0;
while(L){
    if(L & 1){
        ((ret *= R) += A) %= M; 
        (A += B) %= M; // 1引く
    }
    ((A *= R + 1) += B) %= M;
    (B *= 2 * (R + 1)) %= M;
    (R *= R) %= M; // 半分にする
    L >>= 1;
}

まとめ

ダブリングたのしい