結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー しらっ亭しらっ亭
提出日時 2018-04-02 01:00:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 98 ms / 2,000 ms
コード長 925 bytes
コンパイル時間 747 ms
コンパイル使用メモリ 87,128 KB
実行使用メモリ 76,468 KB
最終ジャッジ日時 2023-09-08 13:13:01
合計ジャッジ時間 1,693 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
71,212 KB
testcase_01 AC 91 ms
76,272 KB
testcase_02 AC 98 ms
76,060 KB
testcase_03 AC 91 ms
76,108 KB
testcase_04 AC 97 ms
76,468 KB
testcase_05 AC 94 ms
76,376 KB
testcase_06 AC 93 ms
76,464 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import operator


ZERO = int(False)
ONE = int(True)
TWO = sum([ONE,ONE])
SEVEN = sum([ONE,ONE,ONE,ONE,ONE,ONE,ONE])
NINE = sum([ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE])
TEN = sum([ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE,ONE])

mod = operator.add(pow(TEN, NINE), SEVEN)


def mat_mul(ma, mb):
	ret = [[ZERO,ZERO],[ZERO,ZERO]]
	for i in range(TWO):
		for k in range(TWO):
			for j in range(TWO):
				ret[i][j] = operator.mod(operator.add(ret[i][j], operator.mul(ma[i][k], mb[k][j])), mod);
	return ret


def mat_pow(x, p):
	ret = [[ONE,ZERO],[ZERO,ONE]]

	while (p):
		if p & ONE:
			ret = mat_mul(ret, x)
		x = mat_mul(x, x)
		p = p >> ONE
	return ret


def solve(n):
	if n == ONE:
		return ONE
	mat = [[ONE,ONE],[ONE,ZERO]]
	mat = mat_pow(mat, operator.sub(n, ONE))
	return operator.mod(operator.add(mat[ZERO][ZERO], operator.mul(mat[ZERO][ONE], TWO)), mod)


t = int(input())

for i in range(t):
	n = int(input())
	print(solve(n))
0