結果
問題 |
No.3006 ベイカーの問題
|
ユーザー |
|
提出日時 | 2025-01-17 22:07:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 1,450 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 67,200 KB |
最終ジャッジ日時 | 2025-01-17 22:07:12 |
合計ジャッジ時間 | 2,644 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
MOD = 998244353 def matrix_mult(A, B): """4x4 行列の乗算""" size = 4 return [[sum(A[i][k] * B[k][j] for k in range(size)) % MOD for j in range(size)] for i in range(size)] def matrix_pow(M, p): """4x4 行列の累乗""" size = 4 result = [[1 if i == j else 0 for j in range(size)] for i in range(size)] # 単位行列 base = M while p: if p % 2 == 1: result = matrix_mult(result, base) base = matrix_mult(base, base) p //= 2 return result def solve(X1, Y1, N): # 初期行列 (4x4) base_matrix = [ [X1, -5 * Y1 % MOD, 0, 0], # X_{n+1} = X1 * Xn - 5 * Y1 * Yn [Y1, X1, 0, 0], # Y_{n+1} = X1 * Yn + Y1 * Xn [X1, -5*Y1, 1, 0], # 累積和 An 更新用 [Y1, X1, 0, 1] # 累積和 Bn 更新用 ] # trans = [[X1, X1, X1, X1], [-5*Y1, Y1, -5*Y1, Y1], [0, 0, 1, 0], [0, 0, 0, 1]] # 初期ベクトル initial_vector = [X1, Y1, X1, Y1] # [X1, Y1, A1, B1] # 行列累乗 final_matrix = matrix_pow(base_matrix, N - 1) # 結果の計算 result_vector = [ sum(final_matrix[i][j] * initial_vector[j] for j in range(4)) % MOD for i in range(4) ] # 結果の抽出 final_XN, final_YN, sum_X, sum_Y = result_vector return sum_X, sum_Y # 入力 X1, Y1, N = map(int, input().split()) sum_X, sum_Y = solve(X1, Y1, N) print(sum_X, sum_Y)