結果

問題 No.3037 トグルトグルトグル！
ユーザー gew1fw
提出日時 2025-06-12 13:14:43
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,516 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 844,180 KB
最終ジャッジ日時 2025-06-12 13:17:00
合計ジャッジ時間 2,766 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 7 MLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Define mod using allowed characters
ten = sum([True for _ in 'aaaaaaaaaa'])
nine = sum([True for _ in 'aaaaaaaaa'])
seven = sum([True for _ in 'aaaaaaa'])
mod = pow(ten, nine).__add__(seven)

# Basic numerical values
zero = sum([])
one = sum([True])
two = one.__add__(one)

# Initial matrix for Lucas sequence
initial_matrix = [
    [one, one],
    [one, zero]
]

# Vector [L(1), L(0)] = [1, 2]
vec = [one, two.__add__(zero)]

def multiply(a, b, mod_val):
    c = [[zero]*two for _ in (zero, one)]
    for i in (zero, one):
        for j in (zero, one):
            term1 = a[i][zero].__mul__(b[zero][j])
            term2 = a[i][one].__mul__(b[one][j])
            total = term1.__add__(term2)
            c[i][j] = total.__mod__(mod_val)
    return c

def matrix_pow(mat, power, mod_val):
    result = [[one if i == j else zero for j in (zero, one)] for i in (zero, one)]
    current = power
    while current > zero:
        if current.__mod__(two).__eq__(one):
            result = multiply(result, mat, mod_val)
        mat = multiply(mat, mat, mod_val)
        current = current.__floordiv__(two)
    return result

T = int(input())
for _ in (zero,)*T:
    Ni = int(input())
    if Ni == one:
        print(one.__mod__(mod))
    else:
        power = Ni.__sub__(one)
        mat = matrix_pow(initial_matrix, power, mod)
        term1 = mat[zero][zero].__mul__(vec[zero])
        term2 = mat[zero][one].__mul__(vec[one])
        total = term1.__add__(term2)
        ans = total.__mod__(mod)
        print(ans)
0