問題一覧 >
通常問題
No.3006 ベイカーの問題
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 49
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑
p-adic
問題文最終更新日: 2025-01-11 17:04:52
問題文
入力から与えられる整数 X1,Y1 に対して、Xn,Yn を以下のように帰納的に定める。
Xn+1=X1Xn−5Y1Yn,Yn+1=X1Yn+XnY1.
このとき、X1+X2+⋯+XN と Y1+Y2+⋯+YN を 998244353 で割ったあまりを求めよ。
入力
X1 Y1 N
−1018≤X1,Y1≤1018,
1≤N≤1018
出力
X1+X2+⋯+XN と Y1+Y2+⋯+YN を 998244353 で割ったあまりを、半角空白一字で区切って出力してください。最後に改行してください。
サンプル
サンプル1
入力
1 1 1
出力
1 1
N=1 なので、X1,Y1 をそのまま出力すれば良い。
サンプル2
入力
3 1 2
出力
7 7
X1=3,Y1=1 なので、X2=3×3−5×1×1=4, Y2=3×1+3×1=6.
X1+X2=7, Y1+Y2=7.
サンプル3
入力
1 -1 9
出力
998241312 755
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。