結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー 双六双六
提出日時 2020-07-23 15:44:33
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 886 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 67,652 KB
最終ジャッジ日時 2024-06-23 17:39:11
合計ジャッジ時間 2,481 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
権限があれば一括ダウンロードができます

ソースコード

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