結果

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

ソースコード

diff # 

import sys, operator

def compute_mod():
    ten = ord('\n')
    nine = operator.sub(ten, len('a'))
    seven = ord('\a')
    mod = operator.add(pow(ten, nine), seven)
    return mod

mod = compute_mod()

def matrix_mult(a, b, mod):
    a00, a01 = a[0][0], a[0][1]
    a10, a11 = a[1][0], a[1][1]
    b00, b01 = b[0][0], b[0][1]
    b10, b11 = b[1][0], b[1][1]
    c00_part1 = operator.mul(a00, b00)
    c00_part2 = operator.mul(a01, b10)
    c00 = operator.add(c00_part1, c00_part2)
    c00 = operator.mod(c00, mod)
    c01_part1 = operator.mul(a00, b01)
    c01_part2 = operator.mul(a01, b11)
    c01 = operator.add(c01_part1, c01_part2)
    c01 = operator.mod(c01, mod)
    c10_part1 = operator.mul(a10, b00)
    c10_part2 = operator.mul(a11, b10)
    c10 = operator.add(c10_part1, c10_part2)
    c10 = operator.mod(c10, mod)
    c11_part1 = operator.mul(a10, b01)
    c11_part2 = operator.mul(a11, b11)
    c11 = operator.add(c11_part1, c11_part2)
    c11 = operator.mod(c11, mod)
    return [[c00, c01], [c10, c11]]

def matrix_pow(mat, power, mod):
    zero = len('')
    one = len('a')
    two = len('a''a')
    result = [[one, zero], [zero, one]]
    while operator.gt(power, zero):
        if operator.ne(operator.mod(power, two), zero):
            result = matrix_mult(result, mat, mod)
        mat = matrix_mult(mat, mat, mod)
        power = operator.floordiv(power, two)
    return result

def multiply_matrix_vector(mat, vec, mod):
    a = operator.add(operator.mul(mat[0][0], vec[0]), operator.mul(mat[0][1], vec[1]))
    a = operator.mod(a, mod)
    b = operator.add(operator.mul(mat[1][0], vec[0]), operator.mul(mat[1][1], vec[1]))
    b = operator.mod(b, mod)
    return [a, b]

def lucas(n):
    zero = len('')
    one = len('a')
    two = len('a''a')
    if operator.eq(n, zero):
        return operator.mod(two, mod)
    elif operator.eq(n, one):
        return operator.mod(one, mod)
    else:
        M = [[one, one], [one, zero]]
        power = operator.sub(n, one)
        mat = matrix_pow(M, power, mod)
        vec = [one, two]
        res_vec = multiply_matrix_vector(mat, vec, mod)
        return res_vec[zero]

def main():
    T = int(sys.stdin.readline())
    for _ in 'a' * T:
        n = int(sys.stdin.readline())
        print(lucas(n))

if __name__ == '__main__':
    main()
0