行列累乗で線形遷移を飛ばす

一定の線形変換をK回繰り返すなら、その変換を行列で表し二分累乗できます。

言語：Python / 計算量：d次元なら O(d³ log K)

前提：剰余と組合せを安全に扱う / DPは「同じ続きをまとめる」

考え方

1. 状態ベクトルを決めます。
2. 1ステップの遷移行列を書きます。
3. 単位行列を初期値にして、行列積を二分累乗します。

具体例

F_{n+1}=F_n+F_{n-1} は [F_{n+1},F_n] = [[1,1],[1,0]] [F_n,F_{n-1}]。

実装

p=10**9+7
def mul(a,b):
    return [[sum(a[i][k]*b[k][j] for k in range(2))%p for j in range(2)] for i in range(2)]
a=[[1,1],[1,0]];r=[[1,0],[0,1]];n=10
while n:
    if n&1:r=mul(r,a)
    a=mul(a,a);n>>=1
print(r[0][1])

注意する条件

行列積は一般に順序を交換できません。状態を行ベクトルにするか列ベクトルにするかで式が変わります。

確認問題

F0=0,F1=1 のとき F6 は？

実装課題

N（0≤N≤10^18）。フィボナッチ数F_Nを10^9+7で割った余りを行列累乗で求める。

入力:
10
出力:
55

n=int(input());p=10**9+7
def mul(a,b):
    return [[sum(a[i][k]*b[k][j] for k in range(2))%p for j in range(2)] for i in range(2)]
a=[[1,1],[1,0]];r=[[1,0],[0,1]]
while n:
    if n&1:r=mul(r,a)
    a=mul(a,a);n>>=1
print(r[0][1])

読了の記録・下書き・メモへ