繰り返し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])