結果

問題 No.1595 The Final Digit
ユーザー gr1msl3y
提出日時 2021-11-27 17:37:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 579 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 59,904 KB
最終ジャッジ日時 2024-06-30 08:29:10
合計ジャッジ時間 1,971 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

p, q, r, K = map(int, input().split())
A = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
K -= 1


def product(A, B, MOD):
    h = len(A)
    w = len(B[0])
    res = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            for k in range(len(B)):
                res[i][j] += A[i][k]*B[k][j]
                res[i][j] %= MOD
    return res


M = K.bit_length()
B = [None]*M
B[0] = A
for i in range(1, M):
    B[i] = product(B[i-1], B[i-1], 10)
ans = [[p], [q], [r]]
for i in range(M):
    if (K >> i) & 1:
        ans = product(B[i], ans, 10)

print(ans[0][0])
0