結果

問題 No.2802 Pill Bug in Grid Maze
ユーザー 👑 loop0919
提出日時 2025-12-17 23:58:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,917 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 136 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 848,876 KB
最終ジャッジ日時 2025-12-17 23:58:55
合計ジャッジ時間 4,953 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 4 MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# from lib.math.comb import Comb


# region lib.math.comb
class Comb:
    """\
    nCr % mod を計算する.  
    """

    _limit: int
    _mod: int

    _fac: list[int]
    _inv: list[int]
    _facinv: list[int]

    def __init__(self, limit=10**6, mod=998244353):
        """\
        nCr % mod を計算するための前計算.  
        計算量 O(limit).

        Args:
            limit (int?): nCr を計算するときの n の最大値.
            mod (prime?): mod で割った余り. 素数.
        """
        self._limit = limit
        self._mod = mod

        self._fac = [1] * (limit + 1)
        self._inv = [1] * (limit + 1)
        self._facinv = [1] * (limit + 1)

        for i in range(2, limit + 1):
            self._fac[i] = self._fac[i - 1] * i
            self._inv[i] = mod - self._inv[mod % i] * (mod // i)
            self._facinv[i] = self._facinv[i - 1] * self._inv[i]

    def __call__(self, n: int, r: int) -> int:
        """\
        nCr % mod を計算する.
        クエリ O(1).

        Args:
            n (int): nCr を計算するときの n.
            r (int): nCr を計算するときの r.
        
        Returns:
            nCr % mod の結果.
        """
        assert (
            0 <= n <= self._limit
        ), f"n は 0 以上 {self._limit} である必要があります.: {n=}"

        if n < r:
            return 0

        return (
            self._fac[n] * self._facinv[n - r] % self._mod * self._facinv[r] % self._mod
        )


# endregion

# region Main logic
MOD = 998244353

H, W = [int(s) for s in input().split()]

if H == 1 or W == 1:
    print(1)
    exit()

comb = Comb(max(H - 1, W), MOD)

ans = 0
for i in range(min(2 * H - 2, 2 * W - 1)):
    x = (i + 1) // 2
    y = i // 2
    pow_val = pow(2, (H - 1) * (W - 1) - i, MOD)

    ans += pow_val * comb(W - 1, x) * comb(H - 2, y) % MOD
    ans %= MOD

print(ans)

# endregion
0