[Baekjoon] 11444. フィボナッチ数6[G 2]

📚 質問する

https://www.acmicpc.net/problem/11444

📖 に答える

nは10000000000000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
フィボナッチ数を解決する方法を探しています.
ピサノ周期
ピボナッチを整数で割ると周期が現れます.
ピサノサイクルは非常に大きく、100000007も使えません.
ピサノサイクルを使用する場合、モジュール化演算を実行する値が大きすぎます.
乗算、行列べき乗
O(n)をO(log(n))とする.
点火式をマトリクス化して解く方法.
行列べき乗法が適用されます.
点火式問題の時間的複雑さをO(log(n))に低減した.
まずフィボナッチの点火式を書いて、
F(n) = F(n-1) + F(n-2)
これを行列として表します.n,n−1,n−2の3つの表現を2 x 2行列で表した.
左はnとn−1,右はnとn−2である.
このため、F(n−1)=F(n−1)式を用いる.
マトリクスは以下の通りです.

左と右の項が1項ずつ減算されるのは,行列の繰返し二乗を利用するためである.
ここで点火式のように考えると[[1, 1], [1, 0]]はnの増加に乗じた形で、以下のようになります.

行列の繰返し二乗は分割征服を用いてO(n)をO(logn)に減少させた.
行列を乗じた関数を構築し,セグメント積分により二乗を減らす関数によって解決した.
分割征服を行う際に再帰を用い,二乗が1であれば乗算しない場合であるため,戻り,二乗が2である場合まで演算する.
中間中間中間では,各演算が10000007のモジュール化演算を行う.

📒 コード#コード#

def matrix_s(m):            # 행렬 곱, 입력에는 초기 행렬이나, 현재 결과 행렬만 들어온다.
    a, b = result_arr[0]    # 결과행렬이 들어오는 경우는 제곱, 아니면 곱이다.
    c, d = result_arr[1]
    e, f = m[0]
    g, h = m[1]
    result_arr[0][0] = (a * e + b * g) % 1_000_000_007
    result_arr[0][1] = (a * f + b * h) % 1_000_000_007
    result_arr[1][0] = (c * e + d * g) % 1_000_000_007
    result_arr[1][1] = (c * f + d * h) % 1_000_000_007


def recur(n):   # 거듭제곱 분할정복
    if n == 1:
        return

    if n // 2:
        recur(n // 2)
        matrix_s(result_arr)   # 제곱 연산

    if n % 2:
        matrix_s(first_arr) # 그냥 곱 연산


n = int(input())
first_arr = [[1, 1], [1, 0]]       # 초기 행렬
result_arr = [[1, 1], [1, 0]]      # 결과 행렬
recur(n - 1)
print(result_arr[0][0] % 1_000_000_007)

🔍 結果

点火式で解ける問題を解決する際に、時間の複雑さがO(n)で解決するのが難しい場合は、行列をなんとか利用しましょう~!