結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー kumatan400
提出日時 2022-03-28 05:58:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 861 bytes
コンパイル時間 1,462 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 52,352 KB
最終ジャッジ日時 2024-11-06 22:18:29
合計ジャッジ時間 1,697 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

def mul(X, Y, MOD):
    if len(X[0]) != len(Y):
        return False

    A = len(X)
    B = len(Y[0])
    C = len(X[0])
    res = [[0]*B for _ in range(A)]

    for i in range(A):
        for j in range(B):
            for k in range(C):
                res[i][j] += X[i][k] * Y[k][j]
                res[i][j] %= MOD
    return res




def rui(X, n, MOD):
    if n == 0:
        A = len(X)
        res = [[0]*A for _ in range(A)]
        for i in range(A):
            res[i][i] = 1
        return res

    res = rui(X, n//2, MOD)
    res = mul(res, res, MOD)
    if n % 2 == 1:
        res = mul(res, X, MOD)
    return res



N, M = map(int, input().split())
if N == 1:
    ans = 0
elif N == 2:
    ans = 1
else:
    O = [[1, 0],
         [0, 0]]

    T = [[1, 1],
         [1, 0]]

    A = rui(T, N-2, M)
    A = mul(A, O, M)
    ans = A[0][0]


print(ans)
0