結果

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

ソースコード

diff # 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def II(): return int(input())
def MI(): return map(int,input().split())
def LM(): return list(MI())
def LL(n): return [LM() for _ in range(n)]
def LS(n,remove_br=False): return [list(input())[:-1] if remove_br else list(input()) for _ in range(n)]

def MI_1(): return map(lambda x:int(x)-1,input().split())
def LM_1(): return list(MI_1())
def LL_1(n): return [LM_1() for _ in range(n)]

def bit_count(num):
    length = num.bit_length()
    res = 0
    for i in range(length):
        if num >> i & 1:
            res += 1
    return res

DIJ4 = [[-1,0],[0,-1],[0,1],[1,0]]
DIJ8 = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
MOD = 998244353

def DB(*x):
    global DEBUG_MODE
    if DEBUG_MODE: print(*x)
############
DEBUG_MODE=1
############


def matmul(A, B, mod):
    N = len(A)
    K = len(A[0])
    M = len(B[0])

    c = [[0 for _ in range(M)] for _ in range(N)]

    for i in range(N) :
        for j in range(K) :
            for k in range(M) :
                c[i][k] += A[i][j] * B[j][k] 
                c[i][k] %= mod
    return c

def pow_matrix(A, p, mod):
    n = len(A)
    c = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
    while p > 0 :
        if p%2 == 1 :
            c = matmul(c, A, mod)
        A = matmul(A, A, mod)
        p //= 2
    return c


N,M=MI()
mat = [[0,1],[1,1]]
print(pow_matrix(mat,N-1,M)[0][1])
0