結果

問題 No.3006 ベイカーの問題
コンテスト
ユーザー D M
提出日時 2025-02-20 09:31:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 1,915 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,500 KB
実行使用メモリ 54,408 KB
最終ジャッジ日時 2025-02-20 09:31:09
合計ジャッジ時間 2,504 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input_data = sys.stdin.read().strip().split()
if not input_data:
    sys.exit(0)
X1 = int(input_data[0])
Y1 = int(input_data[1])
N = int(input_data[2])
MOD = 998244353

# Field extension element: a + b*w, with w^2 = -5.
class Elem:
    __slots__ = ("a", "b")
    def __init__(self, a, b):
        self.a = a % MOD
        self.b = b % MOD
    def __add__(self, other):
        return Elem(self.a + other.a, self.b + other.b)
    def __sub__(self, other):
        return Elem(self.a - other.a, self.b - other.b)
    def __mul__(self, other):
        # (a + b*w)*(c + d*w) = (a*c - 5*b*d) + (a*d + b*c)*w
        return Elem(self.a * other.a - 5 * self.b * other.b, self.a * other.b + self.b * other.a)
    def __pow__(self, n):
        result = Elem(1, 0)
        base = self
        while n:
            if n & 1:
                result = result * base
            base = base * base
            n //= 2
        return result
    def inv(self):
        # inverse of a + b*w is (a - b*w) / (a^2 + 5*b^2)
        norm = (self.a * self.a + 5 * self.b * self.b) % MOD
        inv_norm = pow(norm, MOD - 2, MOD)
        return Elem(self.a * inv_norm, -self.b * inv_norm)
    def __truediv__(self, other):
        return self * other.inv()
    def __repr__(self):
        return f"Elem({self.a}, {self.b})"

# Create z1 = X1 + w*Y1 in the field extension.
z1 = Elem(X1, Y1)

# If z1 == 1 mod MOD, then each term equals 1, so X_n = 1, Y_n = 0.
if z1.a % MOD == 1 and z1.b % MOD == 0:
    sx = N % MOD
    sy = 0
    sys.stdout.write(f"{sx} {sy}\n")
    sys.exit(0)

# Compute z1^N using fast exponentiation.
z1N = z1 ** N

# Compute the sum S = z1 + z1^2 + ... + z1^N.
# Using the formula for a geometric series:
# S = z1 * (z1^N - 1) / (z1 - 1)
num = z1N - Elem(1, 0)
S = z1 * num / (z1 - Elem(1, 0))

# S = U + w*V, so answer: Xsum = U, Ysum = V.
sx = S.a % MOD
sy = S.b % MOD
sys.stdout.write(f"{sx} {sy}\n")
0