結果

問題 No.3037 トグルトグルトグル！
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:56:56
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,538 bytes
コンパイル時間 410 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 844,084 KB
最終ジャッジ日時 2025-03-26 15:57:06
合計ジャッジ時間 3,234 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 7 MLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import operator as op

zero = len('')
one = len('a')
two = len('aa')

def compute_mod():
    ten = len('aaaaaaaaaa')
    seven = len('aaaaaaa')
    pow_ten_9 = op.pow(ten, op.sub(ten, one))
    mod = op.add(pow_ten_9, seven)
    return mod

mod = compute_mod()

def mat_mult(a, b):
    a11, a12 = a[0][0], a[0][1]
    a21, a22 = a[1][0], a[1][1]
    b11, b12 = b[0][0], b[0][1]
    b21, b22 = b[1][0], b[1][1]

    c11 = op.add(op.mul(a11, b11), op.mul(a12, b21))
    c12 = op.add(op.mul(a11, b12), op.mul(a12, b22))
    c21 = op.add(op.mul(a21, b11), op.mul(a22, b21))
    c22 = op.add(op.mul(a21, b12), op.mul(a22, b22))

    c11 = op.mod(c11, mod)
    c12 = op.mod(c12, mod)
    c21 = op.mod(c21, mod)
    c22 = op.mod(c22, mod)

    return ((c11, c12), (c21, c22))

def mat_pow(mat, power):
    result = ((one, zero), (zero, one))
    current = mat
    while op.gt(power, zero):
        if op.eq(op.and_(power, one), one):
            result = mat_mult(result, current)
        current = mat_mult(current, current)
        power = op.floordiv(power, two)
    return result

def compute_lucas(n_val):
    if n_val == zero:
        return op.mod(two, mod)
    if n_val == one:
        return op.mod(one, mod)
    M = ((one, one), (one, zero))
    power = op.sub(n_val, one)
    M_pow = mat_pow(M, power)
    new_a = op.add(op.mul(M_pow[0][0], one), op.mul(M_pow[0][1], two))
    return op.mod(new_a, mod)

T = int(sys.stdin.readline())
for _ in (zero,)*T:
    n_val = int(sys.stdin.readline())
    print(compute_lucas(n_val))
0