結果

問題 No.3006 ベイカーの問題
コンテスト
ユーザー Suchmos
提出日時 2025-01-17 23:07:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 982 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 54,376 KB
最終ジャッジ日時 2025-01-17 23:07:56
合計ジャッジ時間 2,467 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod=998244353
import sys;sys.setrecursionlimit(10**6)
X1,Y1,N=map(int,input().split())

def mmul(A,B):
    return [
        [(A[0][0]*B[0][0]+A[0][1]*B[1][0])%mod,(A[0][0]*B[0][1]+A[0][1]*B[1][1])%mod],
        [(A[1][0]*B[0][0]+A[1][1]*B[1][0])%mod,(A[1][0]*B[0][1]+A[1][1]*B[1][1])%mod]
    ]

def madd(A,B):
    return [
        [(A[0][0]+B[0][0])%mod,(A[0][1]+B[0][1])%mod],
        [(A[1][0]+B[1][0])%mod,(A[1][1]+B[1][1])%mod]
    ]

M=[[X1%mod,(-5*Y1)%mod],[Y1%mod,X1%mod]]
idt=[[1,0],[0,1]]
zero=[[0,0],[0,0]]

def powsum(M,n):
    if n==0:
        return (idt,zero)
    if n==1:
        return (M,idt)
    if n%2==0:
        Ah,Sh=powsum(M,n//2)
        Af=mmul(Ah,Ah)
        S=madd(Sh,mmul(Ah,Sh))
        return (Af,S)
    else:
        Apre,Spre=powsum(M,n-1)
        Af=mmul(M,Apre)
        S=madd(Spre,Apre)
        return (Af,S)
    
_,SM=powsum(M,N)
vec=[X1%mod,Y1%mod]
SX=(SM[0][0]*vec[0]+SM[0][1]*vec[1])%mod
SY=(SM[1][0]*vec[0]+SM[1][1]*vec[1])%mod

print(SX,SY)
0