結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー Honjo_Maple
提出日時 2023-07-26 00:17:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 4,415 bytes
コンパイル時間 793 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 64,120 KB
最終ジャッジ日時 2024-10-02 17:01:52
合計ジャッジ時間 1,717 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import bisect, collections, copy, heapq, itertools, math, string
# import decimal # pypy だと遅い
# from collections import defaultdict
# from functools import cmp_to_key
import sys

sys.setrecursionlimit(5 * 10 ** 5)
input = sys.stdin.readline

#region template

from importlib.util import find_spec
if find_spec("pypyjit"):
    import pypyjit
    pypyjit.set_param('max_unroll_recursion=-1')

if "-LOCAL" in sys.argv:
    # debug("x") のように引数を文字列で与える
    def debug(var):
        print("{}: {}".format(var, eval(var)), file = sys.stderr)
    
    from inspect import currentframe
    def DEBUG(var):
        print("Line {}: {}".format(currentframe().f_back.f_lineno, var), file = sys.stderr)
else:
    def debug(var): return
    def DEBUG(var): return

def CNTBIT(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m

def lcm(m, n):
    return m // gcd(m, n) * n

def bisect_ll(is_ok, ok, ng):
    # while not is_ok(ok): ok <<= 1; assert(ok <= (1<<62))
    while abs(ok - ng) > 1:
        mid = (ok + ng) >> 1
        if is_ok(mid): ok = mid
        else: ng = mid
    return ok

def bisect_double(is_ok, ok, ng):
    # while not is_ok(ok): ok *= 2; assert(ok <= (1<<62))
    while abs(ok - ng) > EPSILON:
        mid = (ok + ng) / 2
        if is_ok(mid): ok = mid
        else: ng = mid
    return ok

class Edge:
    def __init__(self, frm, to, cost = 1):
        self.frm = frm
        self.to = to
        self.cost = cost

class Graph:
    def __init__(self, n):
        self.g = [[] for _ in range(n)]
        self.sz = n
    
    def size(self):
        return self.sz
    
    def add_directed_edge(self, frm, to, cost = 1):
        self.g[frm].append(Edge(frm, to, cost))
    
    def add_edge(self, frm, to, cost = 1):
        self.g[frm].append(Edge(frm, to, cost))
        self.g[to].append(Edge(to, frm, cost))
    
    def __getitem__(self, k):
        return self.g[k]

class Enumeration:
    def __init__(self, n, mod):
        assert 0 <= n < mod
        self._n = n
        self._mod = mod
        self._fact = [1] * (n + 1)
        self._finv = [1] * (n + 1)
        self._inv = [1] * (n + 1)
        for i in range(2, n + 1):
            self._fact[i] = self._fact[i - 1] * i % mod
            self._inv[i] = mod - self._inv[mod % i] * (mod // i) % mod
            self._finv[i] = self._finv[i - 1] * self._inv[i] % mod
    
    def fact(self, k):
        return self._fact[k]
    
    def finv(self, k):
        return self._fact[k]
    
    def inv(self, k):
        return self._inv[k]
    
    def C(self, n, k):
        if n < k or k < 0: return 0
        return self._fact[n] * (self._finv[k] * self._finv[n - k] % self._mod) % self._mod
    
    def P(self, n, k):
        if n < k or k < 0: return 0
        return self._fact[n] * self._finv[n - k] % self._mod

#endregion template

INF = 1001001001
INFL = 1001001001001001001
EPSILON = 1e-10
MOD = 998244353
dy = (1, 0, -1, 0, 1, 1, -1, -1)
dx = (0, 1, 0, -1, -1, 1, 1, -1)

#-------------------------- コピペゾーン -------------------------------

def Mat_mul(A, B, mod):
    assert(len(A[0]) == len(B))
    n, l, m = len(A), len(B), len(B[0])
    ret = [[0] * m for _ in range(n)]
    for i in range(n):
        for k in range(l):
            for j in range(m):
                ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % mod
    return ret

def Mat_pow(A, n, mod):
    sz = len(A)
    ret, T = [[0] * sz for _ in range(sz)], [[0] * sz for _ in range(sz)]
    for i in range(sz): ret[i][i] = 1
    for i in range(sz):
        for j in range(sz):
            T[i][j] = A[i][j]
    while n:
        if n & 1:
            ret = Mat_mul(ret, T, mod)
        T = Mat_mul(T, T, mod)
        n >>= 1
    return ret    

#-----------------------------------------------------------------------

if __name__ == "__main__":
    # Write here.
    N, M = map(int, input().split())
    A = [[1, 1], [1, 0]]
    A = Mat_pow(A, N - 2, M)
    print(A[0][0] % M)
    exit(0)
0