結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー tko919
提出日時 2025-12-23 01:18:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,865 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 357 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 93,952 KB
最終ジャッジ日時 2025-12-23 01:18:30
合計ジャッジ時間 9,111 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353


class Fp:
    __slots__ = ("v",)

    def __init__(self, v=0):
        self.v = v % MOD

    def __add__(self, other):
        if not isinstance(other, Fp):
            other = Fp(other)
        return Fp(self.v + other.v)

    def __sub__(self, other):
        if not isinstance(other, Fp):
            other = Fp(other)
        return Fp(self.v - other.v)

    def __mul__(self, other):
        if not isinstance(other, Fp):
            other = Fp(other)
        return Fp(self.v * other.v)

    def __truediv__(self, other):
        if not isinstance(other, Fp):
            other = Fp(other)
        return self * other.inv()

    def __iadd__(self, other):
        if not isinstance(other, Fp):
            other = Fp(other)
        self.v = (self.v + other.v) % MOD
        return self

    def __isub__(self, other):
        if not isinstance(other, Fp):
            other = Fp(other)
        self.v = (self.v - other.v) % MOD
        return self

    def inv(self):
        return Fp(pow(self.v, MOD - 2, MOD))

    def __repr__(self):
        return str(self.v)


def solve(rot):
    n = int(input())

    CB = int(round(n ** (1 / 3)))
    while (CB + 1) ** 3 <= n:
        CB += 1
    while CB**3 > n:
        CB -= 1

    def inside(x, y):
        return x >= 0 and y >= 0 and x * (y + 1) + y * (x + 1) > n

    def cut(x, y, p):
        dx, dy = p
        return (2 * y + 1) * dx <= (2 * x + 1) * dy

    x = int((n // 2) ** 0.5) + 10
    assert inside(x, x)
    while inside(x, x):
        x -= 1

    border = Fp(x)
    x += 1

    y = (n - x) // (2 * x + 1)
    while not inside(x, y):
        y += 1

    ret = Fp(0)
    sbt = [(1, 0), (0, 1)]

    while True:
        dx1, dy1 = sbt.pop()
        while inside(x + dx1, y - dy1):
            if y <= dy1:
                break
            ret += Fp(x * dy1 + (dy1 + 1) * (dx1 - 1) // 2)
            ret -= border * dy1
            x += dx1
            y -= dy1

        if y <= CB:
            break

        dx2, dy2 = dx1, dy1
        while sbt:
            dx1, dy1 = sbt[-1]
            if inside(x + dx1, y - dy1):
                break
            sbt.pop()
            dx2, dy2 = dx1, dy1

        if not sbt:
            break

        while True:
            mx = dx1 + dx2
            my = dy1 + dy2
            if inside(x + mx, y - my):
                dx1, dy1 = mx, my
                sbt.append((dx1, dy1))
            else:
                if cut(x + mx, y - my, (dx1, dy1)):
                    break
                dx2, dy2 = mx, my

    for i in range(1, y):
        add = (n - i) // (2 * i + 1) + 3
        while inside(add, i):
            add -= 1
        ret += Fp(add) - border

    ret = ret * 2 + border * border
    print(ret)


def main():
    t = int(input())
    for rot in range(1, t + 1):
        solve(rot)


if __name__ == "__main__":
    main()
0