結果
問題 | No.1989 Pairing Multiset |
ユーザー |
|
提出日時 | 2022-06-25 01:19:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 1,364 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 59,776 KB |
最終ジャッジ日時 | 2024-11-08 19:47:30 |
合計ジャッジ時間 | 2,304 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
from collections import defaultdictfrom itertools import combinations_with_replacementimport sysinput = sys.stdin.readlinedef iinput(): return int(input())def sinput(): return input().rstrip()def i0input(): return int(input()) - 1def linput(): return list(input().split())def liinput(): return list(map(int, input().split()))def miinput(): return map(int, input().split())def li0input(): return list(map(lambda x: int(x) - 1, input().split()))def mi0input(): return map(lambda x: int(x) - 1, input().split())INF = 10**20MOD = 998244353def modinv(a):b = MODu, v = 1, 0while b > 0:t = a // ba -= t * ba, b = b, au -= t * vu, v = v, ureturn u % MODdef combi(n, k):k = max(k, n-k)ans = 1for i in range(n, k, -1):ans *= ians %= MODtmp = 1for i in range(2, n-k+1):tmp *= itmp %= MODreturn ans * modinv(tmp) % MODdef solve_naive(N, M):ans = 0for res in combinations_with_replacement(range(M+1), 2*N):tmp = 0for i in range(N):tmp += abs(res[2*i] - res[2*i+1])ans += tmpreturn ansdef solve_naive2(N, M):ans = 0for k in range(M+1):ans += k * combi(k+N-1, k) * combi(M+N-k, M-k)return ansN, M = liinput()print(combi(2*N+M, 2*N+1) * N % MOD)