結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー Yuya Ishii
提出日時 2025-06-15 21:47:05
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 437 ms / 2,000 ms
コード長 1,239 bytes
コンパイル時間 418 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 32,112 KB
最終ジャッジ日時 2025-06-15 21:47:14
合計ジャッジ時間 8,008 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
# 標準入力受取：簡素化
INT = lambda : int(sys.stdin.readline().rstrip())
FLOAT = lambda : float(sys.stdin.readline().rstrip())
MI = lambda : map(int, sys.stdin.readline().rstrip().split())
MF = lambda : map(float, sys.stdin.readline().rstrip().split())
MI_DEC = lambda : map(lambda x:int(x)-1, sys.stdin.readline().rstrip().split())
LI = lambda : list(map(int, sys.stdin.readline().rstrip().split()))
LF = lambda : list(map(float, sys.stdin.readline().rstrip().split()))
LI_DEC = lambda : list(map(lambda x: int(x)-1, sys.stdin.readline().rstrip().split()))
LS = lambda : list(sys.stdin.readline().rstrip())
LSS = lambda : sys.stdin.readline().rstrip().split()
IN = lambda :sys.stdin.readline().rstrip()
import numpy as np
memo = {}
keyset = set()
def powmtx(mtx,n,M):   # mtx: matrix, n: power, M: modulo
    if n == 0: return np.eye(len(mtx), dtype='int64')
    if n == 1: return mtx
    if n in keyset:
        return memo[n]
    m2, p2 = mtx, 2
    while p2 <= n:
        m2 = np.mod(m2@m2,M)
        memo[p2] = m2
        keyset.add(p2)
        p2 *= 2
    return np.mod(powmtx(mtx,(n-p2//2),M)@m2,M)


N, M = MI()
S = np.array([1,0])
nexter = np.array([[1,1],[1,0]])

mul = powmtx(nexter,N-1,M)
print((mul@S)[1])
0