結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2020-12-16 00:09:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 193 ms / 3,000 ms |
コード長 | 20,097 bytes |
コンパイル時間 | 3,610 ms |
コンパイル使用メモリ | 231,076 KB |
最終ジャッジ日時 | 2025-01-17 01:15:56 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
//FPS持ってないので うしさん(ei1333さん)のライブラリを借用#include <bits/stdc++.h>using namespace std;using int64 = long long;//const int mod = 1e9 + 7;const int mod = 998244353;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}static constexpr uint32_t mul_inv(uint32_t n, int e = 5, uint32_t x = 1) {return e == 0 ? x : mul_inv(n, e - 1, x * (2 - x * n));}template< uint32_t mod, bool fast = false >struct ModInt2 {using u32 = uint32_t;using u64 = uint64_t;static constexpr u32 inv = mul_inv(mod);static constexpr u32 r2 = -uint64_t(mod) % mod;uint32_t x;ModInt2() : x(0) {}ModInt2(const int64_t &y): x(reduce(u64(fast ? y : (y >= 0 ? y % mod : (mod - (-y) % mod) % mod)) * r2)) {}u32 reduce(const u64 &w) const {return u32(w >> 32) + mod - u32((u64(u32(w) * inv) * mod) >> 32);}ModInt2 &operator+=(const ModInt2 &p) {if(int(x += p.x - 2 * mod) < 0) x += 2 * mod;return *this;}ModInt2 &operator-=(const ModInt2 &p) {if(int(x -= p.x) < 0) x += 2 * mod;return *this;}ModInt2 &operator*=(const ModInt2 &p) {x = reduce(uint64_t(x) * p.x);return *this;}ModInt2 &operator/=(const ModInt2 &p) {*this *= p.inverse();return *this;}ModInt2 operator-() const { return ModInt2() - *this; }ModInt2 operator+(const ModInt2 &p) const { return ModInt2(*this) += p; }ModInt2 operator-(const ModInt2 &p) const { return ModInt2(*this) -= p; }ModInt2 operator*(const ModInt2 &p) const { return ModInt2(*this) *= p; }ModInt2 operator/(const ModInt2 &p) const { return ModInt2(*this) /= p; }bool operator==(const ModInt2 &p) const { return get() == p.get(); }bool operator!=(const ModInt2 &p) const { return get() != p.get(); }int get() const { return reduce(x) % mod; }ModInt2 pow(int64_t n) const {ModInt2 ret(1), mul(*this);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}ModInt2 inverse() const {return pow(mod - 2);}friend ostream &operator<<(ostream &os, const ModInt2 &p) {return os << p.get();}friend istream &operator>>(istream &is, ModInt2 &a) {int64_t t;is >> t;a = ModInt2< mod, fast >(t);return (is);}static int get_mod() { return mod; }};using modint = ModInt2< mod >;template< typename Mint >struct NumberTheoreticTransformFriendlyModInt {vector< Mint > dw, idw;int max_base;Mint root;NumberTheoreticTransformFriendlyModInt() {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;}};/*** @brief Formal-Power-Series(形式的冪級数)*/template< typename T >struct FormalPowerSeries : vector< T > {using vector< T >::vector;using P = FormalPowerSeries;using MULT = function< vector< T >(P, P) >;using FFT = function< void(P &) >;using SQRT = function< T(T) >;static MULT &get_mult() {static MULT mult = nullptr;return mult;}static void set_mult(MULT f) {get_mult() = f;}static FFT &get_fft() {static FFT fft = nullptr;return fft;}static FFT &get_ifft() {static FFT ifft = nullptr;return ifft;}static void set_fft(FFT f, FFT g) {get_fft() = f;get_ifft() = g;if(get_mult() == nullptr) {auto mult = [&](P a, P b) {int need = a.size() + b.size() - 1;int nbase = 1;while((1 << nbase) < need) nbase++;int sz = 1 << nbase;a.resize(sz, T(0));b.resize(sz, T(0));get_fft()(a);get_fft()(b);for(int i = 0; i < sz; i++) a[i] *= b[i];get_ifft()(a);a.resize(need);return a;};set_mult(mult);}}static SQRT &get_sqrt() {static SQRT sqr = nullptr;return sqr;}static void set_sqrt(SQRT sqr) {get_sqrt() = sqr;}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);auto ret = get_mult()(*this, r);return *this = P(begin(ret), end(ret));}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 dot(P r) const {P ret(min(this->size(), r.size()));for(int i = 0; i < ret.size(); i++) ret[i] = (*this)[i] * r[i];return ret;}P pre(int sz) const {return P(begin(*this), begin(*this) + min((int) this->size(), sz));}P operator>>(int sz) const {if(this->size() <= sz) return {};P ret(*this);ret.erase(ret.begin(), ret.begin() + sz);return ret;}P 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;}T operator()(T x) const {T r = 0, w = 1;for(auto &v : *this) {r += w * v;w *= x;}return r;}P diff() const;P integral() const;// F(0) must not be 0P inv_fast() const;P inv(int deg = -1) const;// F(0) must be 1P log(int deg = -1) const;P sqrt(int deg = -1) const;// F(0) must be 0P exp_fast(int deg = -1) const;P exp(int deg = -1) const;P pow(int64_t k, int deg = -1) const;P mod_pow(int64_t k, P g) const;};/*** @brief Integral ($\int f(x) dx$)* @docs docs/integral.md*/template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::integral() const {const int n = (int) this->size();P ret(n + 1);ret[0] = T(0);vector< T > invs(n + 1);invs[1] = 1;for(int i = 2; i <= n; i++) invs[i] = invs[T::get_mod() % i] * (T::get_mod() - T::get_mod() / i);for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] * invs[i + 1];return ret;}/*** @brief Diff ($f'(x)$)* @docs docs/diff.md*/template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::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;}/*** @brief Inv ($\frac {1} {f(x)}$)*/template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::inv_fast() const {assert(((*this)[0]) != T(0));const int n = (int) this->size();P res{T(1) / (*this)[0]};for(int d = 1; d < n; d <<= 1) {P f(2 * d), g(2 * d);for(int j = 0; j < min(n, 2 * d); j++) f[j] = (*this)[j];for(int j = 0; j < d; j++) g[j] = res[j];get_fft()(f);get_fft()(g);for(int j = 0; j < 2 * d; j++) f[j] *= g[j];get_ifft()(f);for(int j = 0; j < d; j++) {f[j] = 0;f[j + d] = -f[j + d];}get_fft()(f);for(int j = 0; j < 2 * d; j++) f[j] *= g[j];get_ifft()(f);for(int j = 0; j < d; j++) f[j] = res[j];res = f;}return res.pre(n);}template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::inv(int deg) const {assert(((*this)[0]) != T(0));const int n = (int) this->size();if(deg == -1) deg = n;if(get_fft() != nullptr) {P ret(*this);ret.resize(deg, T(0));return ret.inv_fast();}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);}/*** @brief Log ($\log {f(x)}$)* @docs docs/log.md*/template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::log(int deg) 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();}/*** @brief Exp ($e^{f(x)}$)* @docs docs/exp.md*/template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::exp_fast(int deg) const {if(deg == -1) deg = this->size();assert((*this)[0] == T(0));P inv;inv.reserve(deg + 1);inv.push_back(T(0));inv.push_back(T(1));auto inplace_integral = [&](P &F) -> void {const int n = (int) F.size();auto mod = T::get_mod();while((int) inv.size() <= n) {int i = inv.size();inv.push_back((-inv[mod % i]) * (mod / i));}F.insert(begin(F), T(0));for(int i = 1; i <= n; i++) F[i] *= inv[i];};auto inplace_diff = [](P &F) -> void {if(F.empty()) return;F.erase(begin(F));T coeff = 1, one = 1;for(int i = 0; i < (int) F.size(); i++) {F[i] *= coeff;coeff += one;}};P b{1, 1 < (int) this->size() ? (*this)[1] : 0}, c{1}, z1, z2{1, 1};for(int m = 2; m < deg; m *= 2) {auto y = b;y.resize(2 * m);get_fft()(y);z1 = z2;P z(m);for(int i = 0; i < m; ++i) z[i] = y[i] * z1[i];get_ifft()(z);fill(begin(z), begin(z) + m / 2, T(0));get_fft()(z);for(int i = 0; i < m; ++i) z[i] *= -z1[i];get_ifft()(z);c.insert(end(c), begin(z) + m / 2, end(z));z2 = c;z2.resize(2 * m);get_fft()(z2);P x(begin(*this), begin(*this) + min< int >(this->size(), m));inplace_diff(x);x.push_back(T(0));get_fft()(x);for(int i = 0; i < m; ++i) x[i] *= y[i];get_ifft()(x);x -= b.diff();x.resize(2 * m);for(int i = 0; i < m - 1; ++i) x[m + i] = x[i], x[i] = T(0);get_fft()(x);for(int i = 0; i < 2 * m; ++i) x[i] *= z2[i];get_ifft()(x);x.pop_back();inplace_integral(x);for(int i = m; i < min< int >(this->size(), 2 * m); ++i) x[i] += (*this)[i];fill(begin(x), begin(x) + m, T(0));get_fft()(x);for(int i = 0; i < 2 * m; ++i) x[i] *= y[i];get_ifft()(x);b.insert(end(b), begin(x) + m, end(x));}return P{begin(b), begin(b) + deg};}template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::exp(int deg) const {assert((*this)[0] == T(0));const int n = (int) this->size();if(deg == -1) deg = n;if(get_fft() != nullptr) {P ret(*this);ret.resize(deg, T(0));return ret.exp_fast(deg);}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);}/*** @brief Pow ($f(x)^k$)*/template< typename T >typename FormalPowerSeries< T >::P FormalPowerSeries< T >::pow(int64_t k, int deg) 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 ret = (((*this * rev) >> i).log() * k).exp() * ((*this)[i].pow(k));if(i * k > deg) return P(deg, T(0));ret = (ret << (i * k)).pre(deg);if(ret.size() < deg) ret.resize(deg, T(0));return ret;}}return *this;}const int MOD = 998244353;using mint = ModInt2< MOD, true >;/*** @brief Scanner(高速入力)*/struct Scanner {public:explicit Scanner(FILE *fp) : fp(fp) {}template< typename T, typename... E >void read(T &t, E &... e) {read_single(t);read(e...);}private:static constexpr size_t line_size = 1 << 16;static constexpr size_t int_digits = 20;char line[line_size + 1] = {};FILE *fp = nullptr;char *st = line;char *ed = line;void read() {}static inline bool is_space(char c) {return c <= ' ';}void reread() {ptrdiff_t len = ed - st;memmove(line, st, len);char *tmp = line + len;ed = tmp + fread(tmp, 1, line_size - len, fp);*ed = 0;st = line;}void skip_space() {while(true) {if(st == ed) reread();while(*st && is_space(*st)) ++st;if(st != ed) return;}}template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >void read_single(T &s) {skip_space();if(st + int_digits >= ed) reread();bool neg = false;if(is_signed< T >::value && *st == '-') {neg = true;++st;}typename make_unsigned< T >::type y = *st++ - '0';while(*st >= '0') {y = 10 * y + *st++ - '0';}s = (neg ? -y : y);}template< typename T, enable_if_t< is_same< T, string >::value, int > = 0 >void read_single(T &s) {s = "";skip_space();while(true) {char *base = st;while(*st && !is_space(*st)) ++st;s += string(base, st);if(st != ed) return;reread();}}template< typename T >void read_single(vector< T > &s) {for(auto &d : s) read(d);}};/*** @brief Printer(高速出力)*/struct Printer {public:explicit Printer(FILE *fp) : fp(fp) {}~Printer() { flush(); }template< bool f = false, typename T, typename... E >void write(const T &t, const E &... e) {if(f) write_single(' ');write_single(t);write< true >(e...);}template< typename... T >void writeln(const T &...t) {write(t...);write_single('\n');}void flush() {fwrite(line, 1, st - line, fp);st = line;}private:FILE *fp = nullptr;static constexpr size_t line_size = 1 << 16;static constexpr size_t int_digits = 20;char line[line_size + 1] = {};char small[32] = {};char *st = line;template< bool f = false >void write() {}void write_single(const char &t) {if(st + 1 >= line + line_size) flush();*st++ = t;}template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >void write_single(T s) {if(st + int_digits >= line + line_size) flush();if(s == 0) {write_single('0');return;}if(s < 0) {write_single('-');s = -s;}char *mp = small + sizeof(small);typename make_unsigned< T >::type y = s;size_t len = 0;while(y > 0) {*--mp = y % 10 + '0';y /= 10;++len;}memmove(st, mp, len);st += len;}void write_single(const string &s) {for(auto &c : s) write_single(c);}void write_single(const char *s) {while(*s != 0) write_single(*s++);}template< typename T >void write_single(const vector< T > &s) {for(size_t i = 0; i < s.size(); i++) {if(i) write_single(' ');write_single(s[i]);}}};int main() {NumberTheoreticTransformFriendlyModInt< mint > ntt;using FPS = FormalPowerSeries< mint >;FPS::set_fft([&](FPS &a) { ntt.ntt(a); }, [&](FPS &a) { ntt.intt(a); });Scanner input(stdin);Printer output(stdout);int N;cin >> N;FPS F(N);modint fac[N];fac[0]=1;for(int i=1;i<N;i++)fac[i]=(fac[i-1]*i);for(int i=0;i<=N-2;i++){modint m = i+1;m/=fac[i];F[i] = m.get();}//for(int i=0;i<=N-2;i++)cout << F[i].get() << endl;F = F.pow(N);//for(int i=0;i<=N-2;i++)cout << F[i].get() << endl;modint ans = F[N-2].get();//cout << ans << endl;for(int i=0;i<N-2;i++)ans/=N;ans*=fac[N-2];cout << ans << endl;}