Day 009-Q4 | 行列累乗

問題

フィボナッチ数列を $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ で定義する。$F_N \bmod (10^9 + 7)$ を求めよ。

制約

$0 \le N \le 10^{18}$

入出力例

入力例 1

出力例 1

入力例 2

1000000000000000000

出力例 2

209783453

ヒント (段階的開示)

ヒント1: 方向性

$N$ が最大 $10^{18}$ のためループ不可。行列の累乗（繰り返し二乗法）を使う。

ヒント2: アプローチ

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$$

ヒント3: 誘導

繰り返し二乗法で $M^N$ を $O(\log N)$ の行列積で計算。

模範解答 (Python)

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def mat_mul(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k] == 0:
                continue
            for j in range(n):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

def mat_pow(M, p):
    n = len(M)
    result = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while p > 0:
        if p & 1:
            result = mat_mul(result, M)
        M = mat_mul(M, M)
        p >>= 1
    return result

def solve():
    N = int(input())
    if N == 0:
        print(0)
        return

    M = [[1, 1], [1, 0]]
    Mn = mat_pow(M, N)
    print(Mn[0][1])

solve()

Step-by-Step 解説

1漸化式の行列表現
$M^N$ の $(0,1)$ 成分が $F_N$ になる。

2繰り返し二乗法
$M^N$ を $O(\log N)$ 回の行列積で求める。

3計算量
行列積 $O(8)$ × $O(\log N)$。

よくあるミス

ミス	原因	正しい書き方
$N=0$ の特殊処理漏れ	$M^0$ = 単位行列だが $F_0 = 0$	$N==0$ のとき 0 を出力
行列の添字ミス	$F_N$ の位置を勘違い	`Mn[0][1]` が $F_N$
mod 取り忘れ	大きい $N$ で桁あふれ	各乗算後に `% MOD`

Day 009-Q4 — 行列累乗

問題

制約