結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー lam6er
提出日時 2025-03-20 20:31:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 1,868 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 61,236 KB
最終ジャッジ日時 2025-03-20 20:32:33
合計ジャッジ時間 1,818 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def multiply(a, b):
    n = len(a)
    p = len(b)
    m = len(b[0]) if p > 0 else 0
    result = [[0] * m for _ in range(n)]
    for i in range(n):
        for k in range(p):
            if a[i][k] == 0:
                continue
            for j in range(m):
                result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD
    return result

def matrix_power(mat, power):
    size = len(mat)
    result = [[0]*size for _ in range(size)]
    for i in range(size):
        result[i][i] = 1
    current = [row[:] for row in mat]
    while power > 0:
        if power % 2 == 1:
            result = multiply(result, current)
        current = multiply(current, current)
        power = power // 2
    return result

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    if M == 0:
        print(0)
        return
    # Calculate F_m and F_{m-1}
    if M == 1:
        Fm = 1
        Fm_1 = 0
    else:
        fib_mat = matrix_power([[1, 1], [1, 0]], M-1)
        Fm = fib_mat[0][0] % MOD
        Fm_1 = fib_mat[0][1] % MOD
    # Compute a = L_m = Fm + 2*Fm_1
    a = (Fm + 2 * Fm_1) % MOD
    # Compute b = -(-1)^m mod MOD
    if M % 2 == 0:
        b = (-1) % MOD  # which is MOD-1
    else:
        b = 1  # because (-1)^(m+1) when m is odd
    # If n is 1, return Fm
    if N == 1:
        print(Fm % MOD)
        return
    # Construct the transformation matrix T
    T = [
        [1, a, b],
        [0, a, b],
        [0, 1, 0]
    ]
    # Compute T^(n-1)
    power = N-1
    Tn = matrix_power(T, power)
    # Initial vector [S1, G1, G0] = [Fm, Fm, 0]
    s_initial = Fm % MOD
    g_initial = Fm % MOD
    gp_initial = 0
    # Multiply Tn with the initial vector
    s_new = (Tn[0][0] * s_initial + Tn[0][1] * g_initial + Tn[0][2] * gp_initial) % MOD
    print(s_new % MOD)

if __name__ == '__main__':
    main()
0