結果
問題 | No.2023 Tiling is Fun |
ユーザー |
![]() |
提出日時 | 2022-07-15 17:41:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 934 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 64,512 KB |
最終ジャッジ日時 | 2024-07-19 11:41:34 |
合計ジャッジ時間 | 1,904 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
def modinv(x: int, mod: int) -> int: """ Z/(mod Z)上でのxの逆元 :param x: 整数 :param mod: 整数 :return: x * y % mod = 1を満たすy """ s, ps, r, pr = 0, 1, mod, x while r != 0: pr, (q, r) = r, divmod(pr, r) ps, s = s, ps - q * s if pr == 1: return ps if ps >= 0 else ps + mod raise ValueError("base is not invertible for the given modulus") def factorials_with_inv(k, mod): """ 0! ... k! とそれらのmod逆元を求めて返す """ fac = [1] * (k + 1) inv = [1] * (k + 1) t = 1 for i in range(1, k + 1): t = (t * i) % mod fac[i] = t t = modinv(t, mod) for i in reversed(range(1, k + 1)): inv[i] = t t = (t * i) % mod return fac, inv mod = 998244353 a, b = map(int, input().split()) a -= 1 b -= 1 fac, inv = factorials_with_inv(a+b, mod) print(fac[a+b]*inv[b]%mod*inv[a]%mod)