結果
問題 | No.1989 Pairing Multiset |
ユーザー |
![]() |
提出日時 | 2022-06-25 00:21:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 1,690 bytes |
コンパイル時間 | 493 ms |
コンパイル使用メモリ | 55,296 KB |
実行使用メモリ | 34,176 KB |
最終ジャッジ日時 | 2024-11-08 19:24:57 |
合計ジャッジ時間 | 2,200 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <cstdio>#include <vector>#include <functional>using namespace std;const int mod = 998244353;int power(int a, int b) {int res = 1;while (b) {if (b % 2) res = res * 1ll * a % mod;a = a * 1ll * a % mod;b /= 2;}return res;}void add(int& u, int v) {u += v;if (u >= mod) u -= mod;}struct ModInt {vector<int> f;vector<int> invf;ModInt(int n) {f.resize(n + 1);invf.resize(n + 1);f[0] = 1;for (int i = 1; i <= n; i++) f[i] = f[i - 1] * 1ll * i % mod;invf[n] = power(f[n], mod - 2);for (int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * 1ll * (i + 1) % mod;}int comb(int n, int m) {if (m > n || m < 0) return 0;return f[n] * 1ll * invf[m] % mod * 1ll * invf[n - m] % mod;}};int main() {int n, m;scanf("%d%d", &n, &m);n *= 2;auto md = ModInt(2 * n);function<int(int, int)> comb = [&](int n, int m) {if (m > n || m < 0) return 0;if (n - m > m) return comb(n, n - m);int res = md.invf[n - m];// printf("time = %d\n", n - m);for (int i = n; i > m; i--) res = res * 1ll * i % mod;return res;};int ans = comb(m + n - 2, n - 1);ans = ans * 1ll * (m + n - 1) % mod * 1ll * (m + n) % mod;ans = ans * 1ll * power(n * 1ll * (n + 1) % mod, mod - 2) % mod;/*for (int i = 1; i <= m; i++) {int way = md.comb(m - i + n - 1, n - 1);// printf("i = %d, way = %d\n", i, way);add(ans, way * 1ll * i % mod);}*/ans = ans * 1ll * (n / 2) % mod;printf("%d\n", ans);return 0;}