結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2020-11-30 08:37:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 438 ms / 3,000 ms |
コード長 | 16,684 bytes |
コンパイル時間 | 3,034 ms |
コンパイル使用メモリ | 202,644 KB |
実行使用メモリ | 13,748 KB |
最終ジャッジ日時 | 2024-09-13 02:14:14 |
合計ジャッジ時間 | 7,611 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#line 1 "verify/FPS.power.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/1302"#line 1 "library/template/template.cpp"/* #region header */#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;// typesusing ll = long long;using ull = unsigned long long;using ld = long double;typedef pair<ll, ll> Pl;typedef pair<int, int> Pi;typedef vector<ll> vl;typedef vector<int> vi;typedef vector<char> vc;template <typename T>using mat = vector<vector<T>>;typedef vector<vector<int>> vvi;typedef vector<vector<long long>> vvl;typedef vector<vector<char>> vvc;// abreviations#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()#define rep_(i, a_, b_, a, b, ...) for (ll i = (a), max_i = (b); i < max_i; i++)#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)#define rrep_(i, a_, b_, a, b, ...) \for (ll i = (b - 1), min_i = (a); i >= min_i; i--)#define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)#define srep(i, a, b, c) for (ll i = (a), max_i = (b); i < max_i; i += c)#define SZ(x) ((int)(x).size())#define pb(x) push_back(x)#define eb(x) emplace_back(x)#define mp make_pair//入出力#define print(x) cout << x << endltemplate <class T>ostream& operator<<(ostream& os, const vector<T>& v) {for (auto& e : v) cout << e << " ";cout << endl;return os;}void scan(int& a) { cin >> a; }void scan(long long& a) { cin >> a; }void scan(char& a) { cin >> a; }void scan(double& a) { cin >> a; }void scan(string& a) { cin >> a; }template <class T>void scan(vector<T>& a) {for (auto& i : a) scan(i);}#define vsum(x) accumulate(all(x), 0LL)#define vmax(a) *max_element(all(a))#define vmin(a) *min_element(all(a))#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))// functions// gcd(0, x) fails.ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }template <class T>bool chmax(T& a, const T& b) {if (a < b) {a = b;return 1;}return 0;}template <class T>bool chmin(T& a, const T& b) {if (b < a) {a = b;return 1;}return 0;}template <typename T>T mypow(T x, ll n) {T ret = 1;while (n > 0) {if (n & 1) (ret *= x);(x *= x);n >>= 1;}return ret;}ll modpow(ll x, ll n, const ll mod) {ll ret = 1;while (n > 0) {if (n & 1) (ret *= x);(x *= x);n >>= 1;x %= mod;ret %= mod;}return ret;}uint64_t my_rand(void) {static uint64_t x = 88172645463325252ULL;x = x ^ (x << 13);x = x ^ (x >> 7);return x = x ^ (x << 17);}int popcnt(ull x) { return __builtin_popcountll(x); }template <typename T>vector<int> IOTA(vector<T> a) {int n = a.size();vector<int> id(n);iota(all(id), 0);sort(all(id), [&](int i, int j) { return a[i] < a[j]; });return id;}struct Timer {clock_t start_time;void start() { start_time = clock(); }int lap() {// return x ms.return (clock() - start_time) * 1000 / CLOCKS_PER_SEC;}};/* #endregion*/// constant#define inf 1000000000ll#define INF 4000000004000000000LL#define endl '\n'const long double eps = 0.000000000000001;const long double PI = 3.141592653589793;#line 3 "verify/FPS.power.test.cpp"// library#line 1 "library/convolution/NTT.cpp"template <typename Mint>struct NTT {vector<Mint> dw, idw;int max_base;Mint root;NTT() {const unsigned Mod = Mint::get_mod();assert(Mod >= 3 && Mod % 2 == 1);auto tmp = Mod - 1;max_base = 0;while (tmp % 2 == 0) tmp >>= 1, max_base++;root = 2;while (root.pow((Mod - 1) >> 1) == 1) root += 1;assert(root.pow(Mod - 1) == 1);dw.resize(max_base);idw.resize(max_base);for (int i = 0; i < max_base; i++) {dw[i] = -root.pow((Mod - 1) >> (i + 2));idw[i] = Mint(1) / dw[i];}}void ntt(vector<Mint> &a) {const int n = (int)a.size();assert((n & (n - 1)) == 0);assert(__builtin_ctz(n) <= max_base);for (int m = n; m >>= 1;) {Mint w = 1;for (int s = 0, k = 0; s < n; s += 2 * m) {for (int i = s, j = s + m; i < s + m; ++i, ++j) {auto x = a[i], y = a[j] * w;a[i] = x + y, a[j] = x - y;}w *= dw[__builtin_ctz(++k)];}}}void intt(vector<Mint> &a, bool f = true) {const int n = (int)a.size();assert((n & (n - 1)) == 0);assert(__builtin_ctz(n) <= max_base);for (int m = 1; m < n; m *= 2) {Mint w = 1;for (int s = 0, k = 0; s < n; s += 2 * m) {for (int i = s, j = s + m; i < s + m; ++i, ++j) {auto x = a[i], y = a[j];a[i] = x + y, a[j] = (x - y) * w;}w *= idw[__builtin_ctz(++k)];}}if (f) {Mint inv_sz = Mint(1) / n;for (int i = 0; i < n; i++) a[i] *= inv_sz;}}vector<Mint> multiply(vector<Mint> a, vector<Mint> b) {int need = a.size() + b.size() - 1;int nbase = 1;while ((1 << nbase) < need) nbase++;int sz = 1 << nbase;a.resize(sz, 0);b.resize(sz, 0);ntt(a);ntt(b);Mint inv_sz = Mint(1) / sz;for (int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;intt(a, false);a.resize(need);return a;}};#line 1 "library/math/FormalPowerSeries.cpp"template <typename T>struct FormalPowerSeries : vector<T> {using vector<T>::vector;using P = FormalPowerSeries;using MULT = function<P(P, P)>;static MULT& get_mult() {static MULT mult = nullptr;return mult;}static void set_fft(MULT f) { get_mult() = f; }// 末尾の0を消すvoid shrink() {while (this->size() && this->back() == T(0)) this->pop_back();}P operator+(const P& r) const { return P(*this) += r; }P operator+(const T& v) const { return P(*this) += v; }P operator-(const P& r) const { return P(*this) -= r; }P operator-(const T& v) const { return P(*this) -= v; }P operator*(const P& r) const { return P(*this) *= r; }P operator*(const T& v) const { return P(*this) *= v; }P operator/(const P& r) const { return P(*this) /= r; }P operator%(const P& r) const { return P(*this) %= r; }P& operator+=(const P& r) {if (r.size() > this->size()) this->resize(r.size());for (int i = 0; i < r.size(); i++) (*this)[i] += r[i];return *this;}P& operator+=(const T& r) {if (this->empty()) this->resize(1);(*this)[0] += r;return *this;}P& operator-=(const P& r) {if (r.size() > this->size()) this->resize(r.size());for (int i = 0; i < r.size(); i++) (*this)[i] -= r[i];shrink();return *this;}P& operator-=(const T& r) {if (this->empty()) this->resize(1);(*this)[0] -= r;shrink();return *this;}P& operator*=(const T& v) {const int n = (int)this->size();for (int k = 0; k < n; k++) (*this)[k] *= v;return *this;}P& operator*=(const P& r) {if (this->empty() || r.empty()) {this->clear();return *this;}assert(get_mult() != nullptr);return *this = get_mult()(*this, r);}P& operator%=(const P& r) { return *this -= *this / r * r; }P operator-() const {P ret(this->size());for (int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];return ret;}P& operator/=(const P& r) {if (this->size() < r.size()) {this->clear();return *this;}int n = this->size() - r.size() + 1;return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);}P pre(int sz) const {return P(begin(*this), begin(*this) + min((int)this->size(), sz));}// f/x^szP operator>>(int sz) const {if (this->size() <= sz) return {};P ret(*this);ret.erase(ret.begin(), ret.begin() + sz);return ret;}// f*x^szP operator<<(int sz) const {P ret(*this);ret.insert(ret.begin(), sz, T(0));return ret;}// 反転P rev(int deg = -1) const {P ret(*this);if (deg != -1) ret.resize(deg, T(0));reverse(begin(ret), end(ret));return ret;}//微分P diff() const {const int n = (int)this->size();P ret(max(0, n - 1));for (int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);return ret;}// 積分P integral() const {const int n = (int)this->size();P ret(n + 1);ret[0] = T(0);for (int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);return ret;}// 1/fのdeg項// F(0) must not be 0P inv(int deg = -1) const {assert(((*this)[0]) != T(0));const int n = (int)this->size();if (deg == -1) deg = n;P ret({T(1) / (*this)[0]});for (int i = 1; i < deg; i <<= 1) {ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);}return ret.pre(deg);}// F(0) must be 1P log(int deg = -1) const {assert((*this)[0] == 1);const int n = (int)this->size();if (deg == -1) deg = n;return (this->diff() * this->inv(deg)).pre(deg - 1).integral();}P sqrt(int deg = -1) const {const int n = (int)this->size();if (deg == -1) deg = n;if ((*this)[0] == T(0)) {for (int i = 1; i < n; i++) {if ((*this)[i] != T(0)) {if (i & 1) return {};if (deg - i / 2 <= 0) break;auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2);if (ret.size() < deg) ret.resize(deg, T(0));return ret;}}return P(deg, 0);}P ret({T(1)});T inv2 = T(1) / T(2);for (int i = 1; i < deg; i <<= 1) {ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;}return ret.pre(deg);}// F(0) must be 0P exp(int deg = -1) const {assert((*this)[0] == T(0));const int n = (int)this->size();if (deg == -1) deg = n;P ret({T(1)});for (int i = 1; i < deg; i <<= 1) {ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);}return ret.pre(deg);}P pow(int64_t k, int deg = -1) const {const int n = (int)this->size();if (deg == -1) deg = n;for (int i = 0; i < n; i++) {if ((*this)[i] != T(0)) {T rev = T(1) / (*this)[i];P C(*this * rev);P D(n - i);for (int j = i; j < n; j++) D[j - i] = C[j];D = (D.log() * k).exp() * (*this)[i].pow(k);P E(deg);if (i * k > deg) return E;auto S = i * k;for (int j = 0; j + S < deg && j < D.size(); j++)E[j + S] = D[j];return E;}}return *this;}//代入T eval(T x) const {T r = 0, w = 1;for (auto& v : *this) {r += w * v;w *= x;}return r;}};// NTT<mint> ntt;// FPS mult_ntt(const FPS::P& a, const FPS::P& b) {// auto ret = ntt.multiply(a, b);// return FPS::P(ret.begin(), ret.end());// }// FPS mult(const FPS::P& a, const FPS::P& b) {// FPS c(a.size() + b.size() - 1);// rep(i, a.size()) rep(j, b.size()) { c[i + j] += a[i] * b[j]; }// return c;// }#line 1 "library/math/combination.cpp"/*** @brief Combination(P, C, H, Stirling number, Bell number)* @docs docs/Combination.md*/template <typename T>struct Combination {vector<T> _fact, _rfact, _inv;Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {_fact[0] = _rfact[sz] = _inv[0] = 1;for (int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;_rfact[sz] /= _fact[sz];for (int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);for (int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];}inline T fact(int k) const { return _fact[k]; }inline T rfact(int k) const { return _rfact[k]; }inline T inv(int k) const { return _inv[k]; }T P(int n, int r) const {if (r < 0 || n < r) return 0;return fact(n) * rfact(n - r);}T C(int p, int q) const {if (q < 0 || p < q) return 0;return fact(p) * rfact(q) * rfact(p - q);}T H(int n, int r) const {if (n < 0 || r < 0) return (0);return r == 0 ? 1 : C(n + r - 1, r);}// O(klog(n))// n個の区別できる玉をk個のグループに分割する場合の数(グループのサイズは1以上)T Stirling(int n, int k) {T res = 0;rep(i, k + 1) {res += (T)((k - i) % 2 ? -1 : 1) * C(k, i) * mypow<T>(i, n);}return res / _fact[k];}// O(klog(n))// n個の区別できる玉をk個のグループに分割する場合の数(グループのサイズは0以上)// もしくは、k個以下の玉の一個以上入ったグループに分けると考えてもいいT Bell(int n, int k) {if (n < k) k = n;vector<T> sm(k + 1);sm[0] = 1;rep(j, 1, k + 1) { sm[j] = sm[j - 1] + (T)(j % 2 ? -1 : 1) / _fact[j]; }T res = 0;rep(i, k + 1) { res += mypow<T>(i, n) / _fact[i] * sm[k - i]; }return res;}};#line 1 "library/mod/modint.cpp"template <int mod>struct modint {int x;modint() : x(0) {}modint(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}modint& operator+=(const modint& p) {if ((x += p.x) >= mod) x -= mod;return *this;}modint& operator-=(const modint& p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}modint& operator*=(const modint& p) {x = (int)(1LL * x * p.x % mod);return *this;}modint& operator/=(const modint& p) {*this *= p.inverse();return *this;}modint operator-() const { return modint(-x); }modint operator+(const modint& p) const { return modint(*this) += p; }modint operator-(const modint& p) const { return modint(*this) -= p; }modint operator*(const modint& p) const { return modint(*this) *= p; }modint operator/(const modint& p) const { return modint(*this) /= p; }bool operator==(const modint& p) const { return x == p.x; }bool operator!=(const modint& p) const { return x != p.x; }modint inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return modint(u);}modint pow(int64_t n) const {modint ret(1), mul(x);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream& operator<<(ostream& os, const modint& p) {return os << p.x;}friend istream& operator>>(istream& is, modint& a) {long long t;is >> t;a = modint<mod>(t);return (is);}static int get_mod() { return mod; }inline int get() { return x; }};#line 8 "verify/FPS.power.test.cpp"using mint = modint<998244353>;using FPS = FormalPowerSeries<mint>;NTT<mint> ntt;FPS mult_ntt(const FPS::P& a, const FPS::P& b) {auto ret = ntt.multiply(a, b);return FPS::P(ret.begin(), ret.end());}// FPS::set_fft(mult_ntt); in mainint main() {FPS::set_fft(mult_ntt);int n;cin >> n;Combination<mint> comb(n);FPS f(n + 1);rep(i, n + 1) { f[i] = (mint)(i + 1) / comb.fact(i); }f = f.pow(n, n);print(f[n - 2] * comb.fact(n - 2) / mypow<mint>(n, n - 2));}