結果

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

ソースコード

diff # 

mod = (len('abcdefghij') ** len('abcdefghi')) + len('abcdefg')  # 1000000007

def add(a, b):
    while b:
        carry = a & b
        a = a ^ b
        b = carry << 1
        a %= mod
        b %= mod
    return a % mod

def multiply(a, b):
    result = 0
    while b:
        if b & 1:
            result = add(result, a)
        a = add(a, a)
        b >>= 1
    return result % mod

def mat_mult(m1, m2):
    a = add(multiply(m1[0][0], m2[0][0]), multiply(m1[0][1], m2[1][0]))
    b = add(multiply(m1[0][0], m2[0][1]), multiply(m1[0][1], m2[1][1]))
    c = add(multiply(m1[1][0], m2[0][0]), multiply(m1[1][1], m2[1][0]))
    d = add(multiply(m1[1][0], m2[0][1]), multiply(m1[1][1], m2[1][1]))
    return [[a % mod, b % mod], [c % mod, d % mod]]

def mat_pow(mat, power):
    result = [[1, 0], [0, 1]]  # Identity matrix
    while power:
        if power & 1:
            result = mat_mult(result, mat)
        mat = mat_mult(mat, mat)
        power >>= 1
    return result

def compute_lucas(n):
    if n == 0:
        return 2 % mod
    one = len('a')  # 1
    two = len('ab')  # 2
    zero = len('')   # 0
    mat = [[one, one], [one, zero]]
    power = n - one
    mat_result = mat_pow(mat, power)
    a = multiply(mat_result[0][0], one)
    b = multiply(mat_result[0][1], two)
    res = add(a, b)
    return res % mod

T = int(input())
for _ in range(T):
    n = int(input())
    print(compute_lucas(n))
0