結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー kamome
提出日時 2019-07-02 00:20:01
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
RE  
実行時間 -
コード長 645 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 505 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 41,400 KB
最終ジャッジ日時 2026-04-02 01:46:21
合計ジャッジ時間 6,692 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/python3
#!coding: utf-8
N=int(input())
def mat2_mul(X, Y):
    Z = [ [0, 0], 
          [0, 0] ]
    for (i,j,k) in product(range(2),range(2),range(2)):
        Z[i][j] += X[i][k] * Y[k][j]%1000000007
    return Z

def mat2_pow(X, n):
    if n == 0:
        return [ [1, 0],
                 [0, 1] ]
    elif n % 2:
        return mat2_mul(X, mat2_pow(X, n-1))  
    else:
        half_pow = mat2_pow(X, n/2)
        return mat2_mul(half_pow, half_pow)

def fib(n):
    if n == 0:
        return 0
    else:
        F = [ [0, 1],
              [1, 1] ]
        return mat2_pow(F, n-1)[1][1]


print(fib(N)*fib(N+1)%1000000007)
exit()
0