結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー ninja-kid
提出日時 2022-11-19 09:56:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 1,329 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 55,168 KB
最終ジャッジ日時 2024-09-20 11:28:38
合計ジャッジ時間 1,755 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3

from bisect import bisect, bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush
from itertools import accumulate, combinations, combinations_with_replacement, product
from math import atan, cos, degrees, factorial, gcd, inf, pi


mod1 = 10**9 + 7
mod2 = 998244353
dpos4 = ((1, 0), (0, 1), (-1, 0), (0, -1))
dpos8 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1))


def main():
    N, M = map(int, input().split())

    def matrix_prod(A, B, mod=0):
        ret = [[0] * len(B[0]) for _ in range(len(A))]
        for i in range(len(A)):
            for j in range(len(B[0])):
                for k in range(len(B)):
                    ret[i][j] += A[i][k] * B[k][j]
                    if mod > 0:
                        ret[i][j] %= mod
        return ret

    def matrix_pow(A, K, mod=0):
        if K == 0:
            I = [[0] * len(A[0]) for _ in range(len(A))]
            for i in range(len(A)):
                I[i][i] = 1
            return I
        ret = matrix_pow(matrix_prod(A, A, mod), K // 2, mod)
        if K % 2 == 1:
            ret = matrix_prod(ret, A, mod)
        return ret

    A = [[1, 1], [1, 0]]
    val = matrix_pow(A, N - 1, M)
    print(val[1][0])


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