結果

問題 No.3037 トグルトグルトグル！
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:16:53
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,372 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 82,820 KB
実行使用メモリ 67,760 KB
最終ジャッジ日時 2025-06-12 13:19:17
合計ジャッジ時間 1,798 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

zero = len([])
one = len([()])
two = len([(),()])
seven = len([(),(),(),(),(),(),()])
nine = len([(),(),(),(),(),(),(),(),()])
ten = len([(),(),(),(),(),(),(),(),(),()])
pow_ten_9 = pow(ten, nine)
mod = sum([pow_ten_9, seven])

def multiply(A, B, mod):
    a = (A[0][0].__mul__(B[0][0])).__add__(A[0][1].__mul__(B[1][0]))
    a = divmod(a, mod)[1]
    b = (A[0][0].__mul__(B[0][1])).__add__(A[0][1].__mul__(B[1][1]))
    b = divmod(b, mod)[1]
    c = (A[1][0].__mul__(B[0][0])).__add__(A[1][1].__mul__(B[1][0]))
    c = divmod(c, mod)[1]
    d = (A[1][0].__mul__(B[0][1])).__add__(A[1][1].__mul__(B[1][1]))
    d = divmod(d, mod)[1]
    return [[a, b], [c, d]]

def matrix_pow(mat, power, mod):
    result = [[one, zero], [zero, one]]
    while power > zero:
        if (power & one) == one:
            result = multiply(result, mat, mod)
        mat = multiply(mat, mat, mod)
        power = power >> one
    return result

T = int(input())
for _ in range(T):
    n = int(input())
    if n == zero:
        ans = divmod(two, mod)[1]
    elif n == one:
        ans = divmod(one, mod)[1]
    else:
        mat = [[one, one], [one, zero]]
        power = n.__sub__(one)
        mat_pow = matrix_pow(mat, power, mod)
        a = mat_pow[0][0]
        b = mat_pow[0][1]
        term = (a.__mul__(one)).__add__(b.__mul__(two))
        ans = divmod(term, mod)[1]
    print(ans)
0