結果
問題 |
No.2303 Frog on Grid
|
ユーザー |
|
提出日時 | 2025-03-12 02:14:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 5,438 bytes |
コンパイル時間 | 617 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 98,108 KB |
最終ジャッジ日時 | 2025-03-12 02:14:36 |
合計ジャッジ時間 | 5,984 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
## https://yukicoder.me/problems/no/2952 from collections import deque MOD = 998244353 class CombinationCalculator: """ modを考慮したPermutation, Combinationを計算するためのクラス """ def __init__(self, size, mod): self.mod = mod self.factorial = [0] * (size + 1) self.factorial[0] = 1 for i in range(1, size + 1): self.factorial[i] = (i * self.factorial[i - 1]) % self.mod self.inv_factorial = [0] * (size + 1) self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod) for i in reversed(range(size)): self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod def calc_combination(self, n, r): if n < 0 or n < r or r < 0: return 0 if r == 0 or n == r: return 1 ans = self.inv_factorial[n - r] * self.inv_factorial[r] ans %= self.mod ans *= self.factorial[n] ans %= self.mod return ans def calc_permutation(self, n, r): if n < 0 or n < r: return 0 ans = self.inv_factorial[n - r] ans *= self.factorial[n] ans %= self.mod return ans class NTT: def __init__(self): self._root = self._make_root() self._invroot = self._make_invroot(self._root) def _reverse_bits(self, n): n = (n >> 16) | (n << 16) n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8) n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4) n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2) n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1) return n def _make_root(self): # 3はMODの原始根, 119乗するとconvolusion, NTT における「基底」の条件を満たす r = pow(3, 119, MOD) return [pow(r, 2 ** i, MOD) for i in range(23, -1, -1)] def _make_invroot(self, root): invroot = [] for i in range(len(root)): invroot.append(pow(root[i], MOD - 2, MOD)) return invroot def _ntt(self, poly, root, rev, max_l): n = len(poly) k = (n - 1).bit_length() step = (max_l) >> k for i, j in enumerate(rev[::step]): if i < j: poly[i], poly[j] = poly[j], poly[i] r = 1 for w in root[1:(k + 1)]: for l in range(0, n, r * 2): wi = 1 for i in range(r): a = (poly[l + i + r] * wi) % MOD a += poly[l + i] a %= MOD b = (-poly[l + i + r] * wi) % MOD b += poly[l + i] b %= MOD poly[l + i] = a poly[l + i + r] = b wi *= w wi %= MOD r <<= 1 def convolution(self, poly_l, poly_r): # 多項式を畳み込んだ時の次数よりも大きい2の冪の長さを求める # (NTTの特性上2の冪乗に乗せるため) len_ans = len(poly_l) + len(poly_r) - 1 if (min(len(poly_l), len(poly_r)) <= 40): return self._combolution_light(poly_l, poly_r) # 2の冪の長さを求める n = 1 max_depth = 0 while n <= len_ans: n *= 2 max_depth += 1 rev = [self._reverse_bits(i) >> (32- max_depth) for i in range(n)] new_poly_l = [0] * n for i in range(len(poly_l)): new_poly_l[i] = poly_l[i] new_poly_r = [0] * n for i in range(len(poly_r)): new_poly_r[i] = poly_r[i] # 数論変換 self._ntt(new_poly_l, self._root, rev, n) self._ntt(new_poly_r, self._root, rev, n) # 畳み込みは各iを代入した値の積で求められる d_ans = [0] * n for i in range(n): d_ans[i] = (new_poly_l[i] * new_poly_r[i]) % MOD # 逆数論変換 self._ntt(d_ans, self._invroot, rev, n) # 最後の定数分割る処理 inv_n = pow(n, MOD - 2, MOD) poly_ans = [0] * len_ans for i in range(len_ans): poly_ans[i] = (d_ans[i] * inv_n) % MOD return poly_ans def _combolution_light(self, poly_l, poly_r): poly_ans = [0] * (len(poly_l) + len(poly_r) - 1) for i in range(len(poly_l)): for j in range(len(poly_r)): poly_ans[i + j] += (poly_l[i] * poly_r[j]) % MOD poly_ans[i + j] %= MOD return poly_ans def main(): H, W = map(int, input().split()) combi = CombinationCalculator(H + W, MOD) poly_h = [] for h in range(H): if 2 * h > H: break x = combi.calc_combination(H - h, h) y = combi.inv_factorial[H - h] poly_h.append((x * y) % MOD) poly_w = [] for w in range(W): if 2 * w > W: break x = combi.calc_combination(W - w, w) y = combi.inv_factorial[W - w] poly_w.append((x * y) % MOD) ntt =NTT() poly = ntt.convolution(poly_h, poly_w) answer = 0 for x in range(len(poly_h) - 1 + len(poly_w) - 1 + 1): z = (poly[x] * combi.factorial[H + W - x]) % MOD answer += z answer %= MOD print(answer) if __name__ == "__main__": main()