結果
問題 | No.1757 Many Many Cards |
ユーザー |
|
提出日時 | 2021-11-20 17:33:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 427 ms / 2,000 ms |
コード長 | 788 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 103,424 KB |
最終ジャッジ日時 | 2024-06-11 19:47:30 |
合計ジャッジ時間 | 8,033 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
MX = 10 ** 6 MOD = 998244353 fact = [1] * (MX + 1) inv = [1] * (MX + 1) fact_inv = [1] * (MX + 1) for i in range(2, MX + 1): fact[i] = (fact[i - 1] * i) % MOD inv[i] = ((- inv[MOD % (i)]) * (MOD // i)) % MOD fact_inv[i] = (fact_inv[i - 1] * inv[i]) % MOD def factorial(n): return fact[n] def inverse(n): return inv[n] def combination(n, r): return (fact[n] * fact_inv[n - r] * fact_inv[r]) % MOD N, M = map(int, input().split()) ans = pow(M, 2 * N + 1, MOD) for k in range(1, min(N + 1, M) + 1): ans_k = combination(N, k - 1) * combination(M, k) % MOD ans_k = ans_k * pow(k, max(0, k - 2), MOD) * factorial(k - 1) * pow(2, k - 1, MOD) % MOD ans_k = ans_k * pow(M - k, 2 * (N - k + 1), MOD) % MOD ans = (ans - ans_k) % MOD print(ans)