結果

問題 No.3006 ベイカーの問題
コンテスト
ユーザー qib
提出日時 2025-01-31 00:44:25
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 770 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 31,712 KB
最終ジャッジ日時 2025-01-31 00:44:38
合計ジャッジ時間 13,130 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import numpy as np

MOD = 998244353

x1, y1, n = map(int, input().split())

a = np.array([[x1, - 5 * y1], [y1, x1]], dtype=int)

def pow(mat, x):
  if x == 0:
    return np.identity(2, dtype=int)
  elif x % 2 == 0:
    half = pow(mat, x // 2) 
    ans = half @ half
    ans %= MOD
    return ans
  else:
    ans = mat @ pow(mat, x - 1)
    ans %= MOD
    return ans

def f(mat, x):
  if x == 1:
    return np.identity(2, dtype=int)
  elif x % 2 == 0:
    half = f(mat, x // 2)
    b = np.identity(2, dtype=int) + pow(mat, x // 2)
    b %= MOD
    ans = b @ half
    ans %= MOD
    return ans
  else:
    ans = f(mat, x - 1) + pow(mat, x - 1)
    ans %= MOD
    return ans

fn = f(a, n) @ np.array([[x1], [y1]], dtype=int)
fn %= MOD
print(*fn.flatten().tolist(), sep=" ")
0