結果

問題 No.3036 Nauclhlt型文字列
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:20:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,386 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 67,560 KB
最終ジャッジ日時 2025-04-16 16:21:49
合計ジャッジ時間 1,733 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

zero = len([])
one = len([[]])
two = len('aa')
five = len('aaaaa')
nine = len('aaaaaaaaa')
seven = len('aaaaaaa')
mod = (five * two) ** nine + seven

def multiply(m1, m2, mod):
    z = len([])
    o = len([[]])
    sum_val = m1[z][z] * m2[z][z] + m1[z][o] * m2[o][z]
    _, a = divmod(sum_val, mod)
    sum_val = m1[z][z] * m2[z][o] + m1[z][o] * m2[o][o]
    _, b = divmod(sum_val, mod)
    sum_val = m1[o][z] * m2[z][z] + m1[o][o] * m2[o][z]
    _, c = divmod(sum_val, mod)
    sum_val = m1[o][z] * m2[z][o] + m1[o][o] * m2[o][o]
    _, d = divmod(sum_val, mod)
    return [[a, b], [c, d]]

def matrix_pow(mat, power, mod):
    z = len([])
    o = len([[]])
    result = [[o, z], [z, o]]
    current = mat
    while power > z:
        _, rem = divmod(power, two)
        if rem == o:
            result = multiply(result, current, mod)
        current = multiply(current, current, mod)
        power = power >> o
    return result

t = int(input())
for _ in range(t):
    N = int(input())
    if N == one:
        _, ans = divmod(one, mod)
        print(ans)
    else:
        mat = [[one, one], [one, zero]]
        power = N - one
        mat_exp = matrix_pow(mat, power, mod)
        z = len([])
        o = len([[]])
        a_row = mat_exp[z]
        vec = [one, two]
        sum_val = a_row[z] * vec[z] + a_row[o] * vec[o]
        _, ans = divmod(sum_val, mod)
        print(ans)
0