結果

問題 No.3037 トグルトグルトグル！
ユーザー lam6er
提出日時 2025-04-15 23:45:54
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,649 bytes
コンパイル時間 350 ms
コンパイル使用メモリ 81,404 KB
実行使用メモリ 66,892 KB
最終ジャッジ日時 2025-04-15 23:48:05
合計ジャッジ時間 1,802 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

one = True
zero = one.__sub__(one)
two = one.__add__(one)
three = two.__add__(one)
four = three.__add__(one)
five = four.__add__(one)
six = five.__add__(one)
seven = six.__add__(one)
ten = five.__add__(five)
hundred = ten.__mul__(ten)
thousand = hundred.__mul__(ten)
million = thousand.__mul__(thousand)
billion = thousand.__mul__(million)
mod = billion.__add__(seven)

M = [[one, one], [one, zero]]

def multiply(a, b, mod):
    a11, a12 = a[0][0], a[0][1]
    a21, a22 = a[1][0], a[1][1]
    b11, b12 = b[0][0], b[0][1]
    b21, b22 = b[1][0], b[1][1]
    c11 = a11.__mul__(b11).__add__(a12.__mul__(b21)).__mod__(mod)
    c12 = a11.__mul__(b12).__add__(a12.__mul__(b22)).__mod__(mod)
    c21 = a21.__mul__(b11).__add__(a22.__mul__(b21)).__mod__(mod)
    c22 = a21.__mul__(b12).__add__(a22.__mul__(b22)).__mod__(mod)
    return [[c11, c12], [c21, c22]]

def matrix_pow(mat, power, mod):
    result = [[one, zero], [zero, one]]
    while power.__gt__(zero):
        if power.__mod__(two).__eq__(one):
            result = multiply(result, mat, mod)
        mat = multiply(mat, mat, mod)
        power = power.__floordiv__(two)
    return result

def multiply_vector(mat, vec, mod):
    a = mat[0][0].__mul__(vec[0]).__add__(mat[0][1].__mul__(vec[1])).__mod__(mod)
    b = mat[1][0].__mul__(vec[0]).__add__(mat[1][1].__mul__(vec[1])).__mod__(mod)
    return [a, b]

T = int(input())
for _ in range(T):
    n = int(input())
    if n.__eq__(one):
        print(one.__mod__(mod))
    else:
        exponent = n.__sub__(one)
        mat = matrix_pow(M, exponent, mod)
        vec = multiply_vector(mat, [one, two], mod)
        print(vec[0].__mod__(mod))
0