結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー しらっ亭しらっ亭
提出日時 2018-04-02 00:59:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 925 bytes
コンパイル時間 1,414 ms
コンパイル使用メモリ 87,036 KB
実行使用メモリ 78,064 KB
最終ジャッジ日時 2023-09-08 13:12:59
合計ジャッジ時間 1,975 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
71,280 KB
testcase_01 AC 87 ms
76,228 KB
testcase_02 AC 114 ms
77,696 KB
testcase_03 AC 115 ms
78,064 KB
testcase_04 AC 116 ms
77,584 KB
testcase_05 AC 114 ms
77,588 KB
testcase_06 AC 115 ms
77,676 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