結果

問題 No.8037 Restricted Lucas (Hard)
コンテスト
ユーザー しらっ亭
提出日時 2018-04-02 01:00:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 925 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 64,128 KB
最終ジャッジ日時 2024-06-26 06:24:56
合計ジャッジ時間 1,228 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

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