結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー 双六
提出日時 2020-07-23 15:44:44
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 886 bytes
コンパイル時間 389 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 44,784 KB
最終ジャッジ日時 2024-06-23 17:39:59
合計ジャッジ時間 13,422 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
import numpy as np
mod = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))

def matrixPow(A, n, N):
	B = np.identity(N, dtype = np.int)
	while n > 0:
		if n & 1 == 1:
			B = (A @ B) % mod
		A = (A @ A) % mod
		n >>= 1
	return B

#処理内容
def main():
	N, M = getlist()
	E = np.identity(2, dtype = np.int)
	s = np.full((2, 1), 1)
	s[1, 0] = 0
	A = np.full((2, 2), 1)
	A[1, 1] = 0
	B = matrixPow(A, M, 2)
	a = B
	b = (matrixPow(B, N, 2) - E)
	inv = B - E
	invp = inv[0, 0] * inv[1, 1] - inv[1, 0] * inv[0, 1]
	c = [[inv[1, 1], -inv[0, 1]], [-inv[1, 0], inv[0, 0]]]
	ans = (((((a @ b) % mod) @ c) % mod) @ s) % mod
	# print(B)
	# print(ans)
	answer = ans[1, 0] * pow(int(invp), mod - 2, mod)
	print(answer % mod)





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