結果

問題 No.3036 Nauclhlt型文字列
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:45:18
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,213 bytes
コンパイル時間 616 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 65,792 KB
最終ジャッジ日時 2025-03-26 15:45:51
合計ジャッジ時間 2,003 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

ten = len('..........')
nine = ten - (len('a') - len(''))
seven = len('aaaaaaa')
mod = pow(ten, nine) + seven

one = len('a') - len('')
zero = len('')
two = len('aa')

def multiply(a, b, mod):
    new = [[zero]*two for _ in range(two)]
    for i in range(two):
        for j in range(two):
            total = zero
            for k in range(two):
                term = a[i][k].__mul__(b[k][j])
                total = total.__add__(term)
            new[i][j] = pow(total, one, mod)
    return new

def matrix_power(mat, power, mod):
    result = [[one if i==j else zero for j in range(two)] for i in range(two)]
    while power > zero:
        if power & one:
            result = multiply(result, mat, mod)
        mat = multiply(mat, mat, mod)
        power = power >> one
    return result

T = int(input())
for _ in range(T):
    Ni = int(input())
    if Ni == zero:
        print(pow(two, one, mod))
        continue
    power = Ni - one
    mat = [[one, one], [one, zero]]
    mat_pow = matrix_power(mat, power, mod)
    a = mat_pow[zero][zero]
    b = mat_pow[zero][one]
    term1 = a.__mul__(one)
    term2 = b.__mul__(two)
    total = term1.__add__(term2)
    ans = pow(total, one, mod)
    print(ans)
0