結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー しらっ亭しらっ亭
提出日時 2018-04-02 00:59:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 925 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 76,380 KB
最終ジャッジ日時 2024-06-26 06:24:55
合計ジャッジ時間 1,339 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,864 KB
testcase_01 AC 52 ms
62,592 KB
testcase_02 AC 83 ms
76,160 KB
testcase_03 AC 82 ms
76,380 KB
testcase_04 AC 83 ms
76,160 KB
testcase_05 AC 84 ms
76,220 KB
testcase_06 AC 86 ms
76,272 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