結果
問題 | No.2582 Random Average^K |
ユーザー | fdironia |
提出日時 | 2023-12-10 00:29:15 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 514 ms / 2,000 ms |
コード長 | 940 bytes |
コンパイル時間 | 735 ms |
コンパイル使用メモリ | 79,216 KB |
実行使用メモリ | 50,364 KB |
最終ジャッジ日時 | 2023-12-10 00:29:19 |
合計ジャッジ時間 | 4,258 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 2 ms
6,548 KB |
testcase_04 | AC | 1 ms
6,548 KB |
testcase_05 | AC | 2 ms
6,548 KB |
testcase_06 | AC | 3 ms
6,548 KB |
testcase_07 | AC | 2 ms
6,548 KB |
testcase_08 | AC | 3 ms
6,548 KB |
testcase_09 | AC | 108 ms
17,376 KB |
testcase_10 | AC | 260 ms
37,656 KB |
testcase_11 | AC | 214 ms
29,524 KB |
testcase_12 | AC | 514 ms
50,364 KB |
testcase_13 | AC | 225 ms
11,276 KB |
testcase_14 | AC | 182 ms
42,464 KB |
testcase_15 | AC | 473 ms
50,152 KB |
testcase_16 | AC | 349 ms
46,560 KB |
testcase_17 | AC | 348 ms
46,560 KB |
ソースコード
#include <iostream> using namespace std; constexpr int Z = 998244353; int bexp(int a, int n) { if (n == 0) { return 1; } if (n % 2 == 1) { return 1ll * a * bexp(a, n - 1) % Z; } int t = bexp(a, n / 2); return 1ll * t * t % Z; } int main() { int n, k; cin >> n >> k; int inv[n+k+1]; for (int i = 0; i <= n + k; i++) { inv[i] = i <= 1 ? i : 1ll * (Z - Z / i) * inv[Z%i] % Z; } int ifac[n+1]; for (int i = 0; i <= n; i++) { ifac[i] = i == 0 ? 1 : 1ll * inv[i] * ifac[i-1] % Z; } int ans = 0; for (int i = 0; i <= n; i++) { int t = 1ll * ifac[i] * ifac[n-i] % Z * bexp(n - i, n + k) % Z; ans = (0ll + ans + (i % 2 == 0 ? 1 : -1) * t + Z) % Z; } ans = 1ll * ans * bexp(inv[n], k) % Z; for (int i = 1; i <= n; i++) { ans = 1ll * ans * inv[k+i] % Z * i % Z; } cout << ans << endl; return 0; }