繰り返し2乗法、行列累乗

繰り返し2乗法

繰り返し2乗法とは、指数を2の累乗の積に分解し、計算を効率化するテクニック。
例えば、$3^{50}$が与えられたとき、
$14 = 2^3 + 2^2 + 2^1$と表せるため、$3^{14} = 3^{2^{2^{2^2}}} × 3^{2^{2^2}} × 3^{2^2}$ と変形できる。

愚直に計算した場合、$O(n)$の計算量になるころを、繰り返し2乗法を使って計算することにより、$O(logn)$の計算量になる。

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
      # ここの処理でx→xの2乗→xの4乗、、、と指数が倍になっていく
        n >>= 1
    return ans

注: ただ、pythonの場合、累乗の組み込み関数のpowで繰り返し2乗法が実装されているため、
実際のところこうした実装を自前でする必要はない。

行列累乗(F - Takahashi's Basics in Education and Learning)

このテクニックを使い、行列の累乗も効率化できる。
行列の累乗への拡張は以下のようにする。

def mat_mul(a, b) :
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0] * J for _ in range(I)]
    for i in range(I) :
        for j in range(J) :
            for k in range(K) :
                c[i][j] += a[i][k] * b[k][j]
            c[i][j] %= m
    return c


def mat_pow(x, n):
    y = [[0] * len(x) for _ in range(len(x))]

    for i in range(len(x)):
        y[i][i] = 1

    while n > 0:
        if n & 1:
            y = mat_mul(x, y)
        x = mat_mul(x, x)
        n >>= 1

    return y


l, a, b, m = LI()
d0 = 0
ret = [[0], [a], [1]]
for i in range(1, 19):
    if 10 ** i - 1 - a < 0:
        continue
    d1 = min((10 ** i - 1 - a) // b + 1, l)
    mat = [[10 ** i, 1, 0], [0, 1, b], [0, 0, 1]]
    ret = mat_mul(mat_pow(mat, d1 - d0), ret)
    if d1 == l:
        break
    d0 = d1


//　行列計算の順番によって答えが変わる
// 上の例だと、正方形の右側に縦一列の行列がある
// 正方形の中で入力が横、出力が縦のイメージ。行列の順番が逆
//　だと逆になる

print(ret[0][0])