結果
問題 | No.1960 Guruguru Permutation |
ユーザー |
![]() |
提出日時 | 2022-05-27 23:11:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,041 bytes |
コンパイル時間 | 1,142 ms |
コンパイル使用メモリ | 51,456 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 16:20:45 |
合計ジャッジ時間 | 1,753 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <cstdio>#include <vector>using namespace std;const int mod = 998244353;struct ModInt {vector<int> f;vector<int> invf;ModInt(int n) {f.resize(n + 1);f[0] = 1;for (int i = 1; i <= n; i++) f[i] = f[i - 1] * 1ll * i % mod;invf.resize(n + 1);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 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;}int comb(int n, int m) {if (m > n || m < 0) return 0;return f[n] * 1ll * invf[n - m] % mod * 1ll * invf[m] % mod;}};void add(int& u, int v) {u += v;if (u >= mod) u -= mod;}void sub(int& u, int v) {u -= v;if (u < 0) u += mod;}int main() {int n, m, k;scanf("%d%d%d", &n, &m, &k);auto md = ModInt(n);if (m == 0 && k == 0) {printf("%d\n", md.f[n]);return 0;}int ans = 0;if (k + m <= n) {int left = n - m - k;int mul = md.f[left];for (int i = 1; i <= n - m - k; i++) {int low = m + k;int up = m + k + i - 1;int way = md.f[up];if (low - 1 >= 0) way = way * 1ll * md.invf[low - 1] % mod;way = way * 1ll * md.f[n - m - k - i] % mod;way = way * 1ll * md.comb(left, i) % mod;add(mul, way);}for (int i = 0; i <= min(m, k); i++) {int way = md.comb(m, i) * 1ll * md.comb(k, i) % mod * 1ll * md.f[i]% mod;way = way * 1ll * mul % mod;add(ans, way);}} else {int l = n - k, r = n - m;for (int i = 0; i <= min(l, r); i++) {int way = md.comb(l, i) * 1ll * md.comb(r, i) % mod * 1ll * md.f[i] % mod;add(ans, way);}}printf("%d\n", ans);return 0;}