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

ダブリングとは?

2倍する or 1足すを $O(\log N)$ 回繰り返すだけで $N$ に到達できることを利用したもの全般半分にする or 1引くを繰り返して $N$ を $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$ 桁)

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

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

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

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

以下のコードで、 $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;
}