結果

問題 No.534 フィボナッチフィボナッチ数
ユーザー lam6er
提出日時 2025-03-20 20:29:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 773 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 54,020 KB
最終ジャッジ日時 2025-03-20 20:30:33
合計ジャッジ時間 2,839 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def calc_fib(n, mod):
    if mod == 0:
        return 0
    if n == 0:
        return 0
    # Generate the binary digits of n, MSB to LSB
    bits = []
    m = n
    while m > 0:
        bits.append(m % 2)
        m >>= 1
    bits.reverse()
    a, b = 0, 1  # F(0), F(1)
    for bit in bits:
        c = a * (2 * b - a) % mod
        d = (a * a + b * b) % mod
        if bit:
            a, b = d % mod, (c + d) % mod
        else:
            a, b = c % mod, d % mod
    return a

n = int(input())
tau = 2 * (MOD + 1)  # Calculated Pisano period for MOD = 10^9 + 7

# Calculate fib(n) mod tau to handle huge Fibonacci numbers
fib_n_mod_tau = calc_fib(n, tau)
# Calculate fib(fib_n_mod_tau) mod MOD
result = calc_fib(fib_n_mod_tau, MOD)
print(result % MOD)
0