結果

問題 No.3006 ベイカーの問題
コンテスト
ユーザー tassei903
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0