結果

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

ソースコード

diff # 

import operator

def multiply(a, b, mod):
    a00, a01 = a[0]
    a10, a11 = a[1]
    b00, b01 = b[0]
    b10, b11 = b[1]
    
    c00 = operator.add(operator.mul(a00, b00), operator.mul(a01, b10))
    c01 = operator.add(operator.mul(a00, b01), operator.mul(a01, b11))
    c10 = operator.add(operator.mul(a10, b00), operator.mul(a11, b10))
    c11 = operator.add(operator.mul(a10, b01), operator.mul(a11, b11))
    
    mod_val = mod
    return [
        [
            c00 % mod_val,
            c01 % mod_val
        ],
        [
            c10 % mod_val,
            c11 % mod_val
        ]
    ]

def matrix_power(matrix, power, mod):
    result = [
        [True, False],
        [False, True]
    ]
    while power > 0:
        if (power & True) == True:
            result = multiply(result, matrix, mod)
        matrix = multiply(matrix, matrix, mod)
        power = power >> 1
    return result

def multiply_matrix_vector(matrix, vector, mod):
    a, b = matrix[0]
    c, d = matrix[1]
    x, y = vector
    
    new_x = operator.add(operator.mul(a, x), operator.mul(b, y))
    new_y = operator.add(operator.mul(c, x), operator.mul(d, y))
    
    return [new_x % mod, new_y % mod]

ten = (True << 3) | (True << 1)
nine = (True << 3) | True
seven = (True << 2) | (True << 1) | True
MOD = operator.add(operator.pow(ten, nine), seven)

T = int(input())
for _ in range(T):
    Ni = int(input())
    if Ni == False:
        print((True << True) % MOD)
    elif Ni == True:
        print(True % MOD)
    else:
        matrix = [[True, True], [True, False]]
        power = operator.sub(Ni, True)
        matrix_pow = matrix_power(matrix, power, MOD)
        initial_vector = [True, (True << True)]
        result_vector = multiply_matrix_vector(matrix_pow, initial_vector, MOD)
        print(result_vector[0] % MOD)
0