結果
問題 | No.1302 Random Tree Score |
ユーザー |
|
提出日時 | 2020-11-27 22:33:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 3,000 ms |
コード長 | 1,512 bytes |
コンパイル時間 | 2,301 ms |
コンパイル使用メモリ | 112,588 KB |
最終ジャッジ日時 | 2025-01-16 07:57:05 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#line 2 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/Number/combination.hpp"#include <vector>template <class T>struct Combination {int max_n;std::vector<T> f, invf;explicit Combination(int n): max_n(n), f(n + 1), invf(n + 1) {f[0] = 1;for (int i = 1; i <= n; ++i) {f[i] = f[i - 1] * i;}invf[max_n] = f[max_n].inv();for (int i = max_n - 1; i >= 0; --i) {invf[i] = invf[i + 1] * (i + 1);}}T fact(int n) const { return n < 0 ? T(0) : f[n]; }T invfact(int n) const { return n < 0 ? T(0) : invf[n]; }T perm(int a, int b) const {return a < b || b < 0 ? T(0) : f[a] * invf[a - b];}T binom(int a, int b) const {return a < b || b < 0 ? T(0) : f[a] * invf[a - b] * invf[b];}};#line 2 "main.cpp"#include <atcoder/modint>#include <atcoder/convolution>#include <iostream>#line 6 "main.cpp"using namespace std;using mint = atcoder::modint998244353;const Combination<mint> C(200000);void solve() {int n;cin >> n;vector<mint> binom(n + 1), expo(n + 1);mint p = 1;for (int k = 0; k <= n; ++k) {binom[k] = C.binom(n, k);expo[k] = p * C.invfact(k);p *= n;}auto f = atcoder::convolution(binom, expo);cout << (f[n - 2] * C.fact(n - 2) / mint(n).pow(n - 2)).val() << "\n";}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}