#1195929 (C++23) No.1302 Random Tree Score

• 問題: No.1302 Random Tree Score
• ユーザー: iastm
• 提出日時: 2026-10-30 12:54:16
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 239 ms / 3,000 ms
• コード長: 22,860 bytes
• コンパイル時間: 2,778 ms
• コンパイル使用メモリ: 231,276 KB
• 実行使用メモリ: 11,028 KB
• 最終ジャッジ日時: 2026-10-30 12:54:37
• 合計ジャッジ時間: 6,539 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge7_0

ファイルパターン	結果
sample	AC * 3
other	AC * 13

ソースコード

#include <iostream>
#include <vector>
#include <atcoder/modint>
// #include <kotone/formal_power_series>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_FORMAL_POWER_SERIES_HPP
#define KOTONE_FORMAL_POWER_SERIES_HPP 1

#include <vector>
#include <algorithm>
#include <cassert>
#include <atcoder/convolution>
// #include <kotone/internal_type_traits>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_INTERNAL_TYPE_TRAITS_HPP
#define KOTONE_INTERNAL_TYPE_TRAITS_HPP 1

#include <concepts>

namespace kotone {

template <typename T> concept number = std::is_arithmetic_v<T>;

template <typename T> concept signed_number = std::signed_integral<T> || std::floating_point<T>;

template <typename mint> concept compatible_modint = requires(mint a, mint b, int64_t x) {
    { mint::mod() } -> std::convertible_to<int>;
    mint{};
    mint{1};
    mint{x};

    { a + b }       -> std::same_as<mint>;
    { a - b }       -> std::same_as<mint>;
    { -a }          -> std::same_as<mint>;
    { a * b }       -> std::same_as<mint>;
    { a / b }       -> std::same_as<mint>;
    { a.inv() }     -> std::same_as<mint>;
    { a.pow(x) }    -> std::same_as<mint>;

    { a += b }      -> std::same_as<mint&>;
    { a -= b }      -> std::same_as<mint&>;
    { a *= b }      -> std::same_as<mint&>;
    { a /= b }      -> std::same_as<mint&>;

    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
    { a.val() }     -> std::convertible_to<int>;
};

template <typename T> concept additive = requires(T a, T b) {
    T{};
    { a + b }       -> std::same_as<T>;
    { a - b }       -> std::same_as<T>;
    { -a }          -> std::same_as<T>;
    { a == b }      -> std::convertible_to<bool>;
    { a != b }      -> std::convertible_to<bool>;
};

template <typename T> concept mutable_additive = (
    additive<T>
    && requires(T a, T b) {
        { a += b }  -> std::same_as<T&>;
        { a -= b }  -> std::same_as<T&>;
        { ++a }     -> std::same_as<T&>;
        { --a }     -> std::same_as<T&>;
        { a++ }     -> std::same_as<T>;
        { a-- }     -> std::same_as<T>;
    }
);

}  // namespace kotone

#endif  // KOTONE_INTERNAL_TYPE_TRAITS

namespace kotone {

// A formal power series (`fps`) inherited from `vector<mint>` that supports various operations.
template <compatible_modint mint, bool using_ntt = true> struct formal_power_series : std::vector<mint> {
    using fps = formal_power_series;
    using std::vector<mint>::vector;
    using std::vector<mint>::operator=;

    // Adds `other` to `*this`.
    fps& operator+=(const fps &other) {
        if (this->size() < other.size()) this->resize(other.size());
        for (std::size_t i = 0; i < other.size(); i++) (*this)[i] += other[i];
        return *this;
    }

    // Subtracts `other` from `*this`.
    fps& operator-=(const fps &other) {
        if (this->size() < other.size()) this->resize(other.size());
        for (std::size_t i = 0; i < other.size(); i++) (*this)[i] -= other[i];
        return *this;
    }

    // Multiplies `*this` by `other`.
    fps& operator*=(const fps &other) {
        if (this->empty() || other.empty()) this->clear();
        else if constexpr (using_ntt) *this = atcoder::convolution(*this, other);
        else {
            fps result(this->size() + other.size() - 1);
            for (std::size_t i = 0; i < this->size(); i++) {
                for (std::size_t j = 0; j < other.size(); j++) {
                    result[i + j] += (*this)[i] * other[j];
                }
            }
            *this = result;
        }
        return *this;
    }

    // Multiplies each coefficient by `m`.
    fps& operator*=(const mint &m) { for (mint &c : *this) c *= m; return *this; }
    // Divides each coefficient by `m`.
    // Requires `m != 0`.
    fps& operator/=(const mint &m) { assert(m != 0); for (mint &c : *this) c /= m; return *this; }

    // Returns a copy of `*this`.
    fps operator+() const { return *this; }
    // Returns a copy of negated `*this`.
    fps operator-() const { return fps{} - *this; }

    // Returns `*this` evaluated at `m`.
    mint operator()(const mint &m) const {
        mint result = 0;
        for (std::size_t i = this->size(); i--;) {
            result *= m;
            result += (*this)[i];
        }
        return result;
    }

    // Strips trailing `0`'s.
    void strip() { while (this->size() && this->back() == 0) this->pop_back(); }

    // Divides `*this` by `other` and assigns the quotient to `*this`.
    // Requires `other` to contain nonzero coefficients.
    fps& operator/=(const fps &other) {
        fps denom(other.begin(), other.end());
        denom.strip();
        assert(!denom.empty());
        fps num(this->begin(), this->end());
        num.strip();
        int n = num.size(), m = denom.size();
        if (n < m) {
            this->clear();
            return *this;
        }
        std::reverse(denom.begin(), denom.end());
        std::reverse(num.begin(), num.end());
        *this = num * inverse(denom, n - m + 1);
        this->resize(n - m + 1);
        std::reverse(this->begin(), this->end());
        return *this;
    }

    // Divides `*this` by `other` and assigns the remainder to `*this`.
    // Requires `other` to contain nonzero coefficients.
    fps& operator%=(const fps &other) {
        fps denom(other.begin(), other.end());
        denom.strip();
        assert(!denom.empty());
        fps num(this->begin(), this->end());
        num.strip();
        int n = num.size(), m = denom.size();
        if (n < m) return *this;
        std::reverse(denom.begin(), denom.end());
        std::reverse(num.begin(), num.end());
        fps quo = num * inverse(denom, n - m + 1);
        quo.resize(n - m + 1);
        std::reverse(quo.begin(), quo.end());
        *this -= quo * other;
        this->resize(m - 1);
        return *this;
    }

    // Returns a `vector` containing the results of evaluating `*this` at each point in `vec`.
    std::vector<mint> eval(const std::vector<mint> &vec) {
        int m = vec.size(), len = 1;
        while (len < m) len *= 2;
        std::vector<fps> nodes(len * 2);
        for (int i = 0; i < m; i++) nodes[len + i] = {-vec[i], 1};
        for (int i = m; i < len; i++) nodes[len + i] = {1};
        for (int i = len - 1; i > 0; i--) nodes[i] = nodes[i * 2] * nodes[i * 2 + 1];
        std::vector<mint> result(m);
        auto solve = [&](auto &solve, int i, fps poly) {
            if (i >= len + m) return;
            poly %= nodes[i];
            if (i >= len) {
                result[i - len] = poly[0];
                return;
            }
            solve(solve, i * 2, poly);
            solve(solve, i * 2 + 1, poly);
        };
        solve(solve, 1, *this);
        return result;
    }

    // Returns the sum of `a` and `b`.
    friend fps operator+(const fps &a, const fps &b) { fps c = a; return c += b; }
    // Returns the difference of `a` and `b`.
    friend fps operator-(const fps &a, const fps &b) { fps c = a; return c -= b; }
    // Returns the product of `a` and `b`.
    friend fps operator*(const fps &a, const fps &b) { fps c = a; return c *= b; }
    // Returns `a` with its coefficients multiplied by `b`.
    friend fps operator*(const fps &a, const mint &b) { fps c = a; return c *= b; }
    // Returns `b` with its coefficients multiplied by `a`.
    friend fps operator*(const mint &a, const fps &b) { return b * a; }
    // Returns `a` with its coefficients divided by `b`.
    // Requires `b != 0`.
    friend fps operator/(const fps &a, const mint &b) { assert(b != 0); fps c = a; return c /= b; }
    // Returns the quotient of `a` and `b`.
    // Requires `b` to contain nonzero coefficients.
    friend fps operator/(const fps &a, const fps &b) { fps c = a; return c /= b; }
    // Returns the remainder of `a` and `b`.
    // Requires `b` to contain nonzero coefficients.
    friend fps operator%(const fps &a, const fps &b) { fps c = a; return c %= b; }

    // Returns the inverse of `f` up to the first `n` coefficients.
    // Requires `!f.empty()`.
    // Requires `f[0] != 0`.
    // Requires `n >= 0`.
    static fps inverse(const fps &f, int n) {
        assert(!f.empty());
        assert(f[0] != 0);
        assert(n >= 0);
        if (n == 0) return {};
        fps result{f[0].inv()};
        int m = 1;
        int len = f.size();
        while (m < n) {
            m = std::min(m * 2, n);
            fps sub(f.begin(), f.begin() + std::min(m, len));
            if (m > len) sub.resize(m);
            fps prod = result * sub;
            prod.resize(m);
            prod[0] = 2 - prod[0];
            for (int i = 1; i < m; i++) prod[i] = -prod[i];
            result *= prod;
            result.resize(m);
        }
        result.resize(n);
        return result;
    }

    // Returns a `pair` containing the quotient and remainder of `f` and `g`.
    // Requires `g` to contain nonzero coefficients.
    static std::pair<fps, fps> divmod(const fps &f, const fps &g) {
        fps denom(g.begin(), g.end());
        denom.strip();
        assert(!denom.empty());
        fps num(f.begin(), f.end());
        num.strip();
        int n = num.size(), m = denom.size();
        if (n < m) return {{}, f};
        std::reverse(denom.begin(), denom.end());
        std::reverse(num.begin(), num.end());
        fps quo = num * inverse(denom, n - m + 1);
        quo.resize(n - m + 1);
        std::reverse(quo.begin(), quo.end());
        std::reverse(num.begin(), num.end());
        num -= quo * g;
        num.resize(m - 1);
        return {quo, num};
    }

    // Returns the derivative of `f`.
    // Returns an empty vector if `f` is empty.
    static fps derivative(const fps &f) {
        if (f.empty()) return {};
        fps result(f.begin() + 1, f.end());
        for (std::size_t i = 0; i < result.size(); i++) result[i] *= i + 1;
        return result;
    }

    // Returns the integral of `f`.
    // Sets the `0`-th coefficent of the integral as `0`.
    // If `f` is empty, returns an empty vector.
    static fps integral(const fps &f) {
        if (f.empty()) return {};
        int len = f.size();
        fps result(len + 1);
        result[1] = 1;
        for (int i = 2, p = mint::mod(); i <= len; i++) {
            result[i] = p / i * -result[p % i];
        }
        for (int i = 0; i < len; i++) result[i + 1] *= f[i];
        return result;
    }

    // Returns the logarithm of `f` up to the first `n` coefficients.
    // Requires `!f.empty()`.
    // Requires `f[0] == 1`.
    // Requires `n >= 0`.
    static fps logarithm(const fps &f, int n) {
        assert(!f.empty());
        assert(f[0] == 1);
        assert(n >= 0);
        if (n == 0) return {};
        fps prod;
        if (int len = f.size(); len <= n) prod = derivative(f);
        else prod = derivative({f.begin(), f.begin() + n});
        prod *= inverse(f, n - 1);
        prod.resize(n - 1);
        fps result = integral(prod);
        result.resize(n);
        return result;
    }

    // Returns the exponential of `f` up to the first `n` coefficients.
    // Requires `f.empty() || f[0] == 0`.
    // Requires `n >= 0`.
    static fps exponential(const fps &f, int n) {
        assert(f.empty() || f[0] == 0);
        assert(n >= 0);
        if (n == 0) return {};
        fps result{1};
        if (f.empty()) {
            result.resize(n);
            return result;
        }
        int m = 1;
        int len = f.size();
        while (m < n) {
            m = std::min(m * 2, n);
            fps log = -logarithm(result, m);
            for (int i = 0; i < m && i < len; i++) log[i] += f[i];
            log[0]++;
            result *= log;
            result.resize(m);
        }
        return result;
    }

    // Returns `f` raised to the specified `pow` up to the first `n` coefficients.
    // If `pow == 0`, the resulting `fps` is equivalent to `1`.
    // If `pow > 0 && f.empty()`, the resulting `fps` is equivalent to `0`.
    // Requires `pow >= 0`.
    // Requires `n >= 0`.
    static fps power(const fps &f, int64_t pow, int n) {
        assert(pow >= 0);
        assert(n >= 0);
        if (n == 0) return {};
        if (pow == 0) {
            fps result(n);
            result[0] = 1;
            return result;
        }
        int d = -1;
        {
            int64_t len = f.size();
            int64_t q = (n + pow - 1) / pow;
            if (q > len) q = len;
            for (int i = 0; i < q; i++) {
                if (f[i] == 0) continue;
                d = i;
                break;
            }
            if (d == -1) return fps(n);
        }
        int shift = d * pow;
        int len = f.size() - d;
        if (len > n - shift) len = n - shift;
        fps g(f.begin() + d, f.begin() + d + len);
        mint acc = g[0].pow(pow);
        g = logarithm(g / g[0], n - shift) * pow;
        g = exponential(g, n - shift) * acc;
        fps result(n);
        for (int i = 0; i + shift < n; i++) result[i + shift] = g[i];
        return result;
    }

    // Computes the coefficient of the term with the specified degree `k` in the rational function.
    // Requires `!denominator.empty() && denominator[0] != 0`.
    // Requires `k >= 0`.
    // Reference: https://info.atcoder.jp/entry/algorithm_lectures/linearly_recurrent_sequence_kth_term
    static mint bostan_mori(fps numerator, fps denominator, int64_t k) {
        assert(!denominator.empty() && denominator[0] != 0);
        assert(k >= 0);
        if (numerator.empty()) return 0;
        while (k) {
            fps denom_neg = denominator;
            for (std::size_t i = 1; i < denom_neg.size(); i += 2) {
                denom_neg[i] = -denom_neg[i];
            }
            numerator *= denom_neg;
            denominator *= denom_neg;
            fps new_num, new_denom;
            new_num.reserve((numerator.size() + 1) >> 1);
            new_denom.reserve((denominator.size() + 1) >> 1);
            for (std::size_t i = k & 1; i < numerator.size(); i += 2) new_num.push_back(numerator[i]);
            for (std::size_t i = 0; i < denominator.size(); i += 2) new_denom.push_back(denominator[i]);
            numerator = new_num;
            denominator = new_denom;
            k >>= 1;
        }
        return numerator[0] / denominator[0];
    }

    // Computes term `a[k]` of a homogeneous linear recurrence `a` of order `n`.
    // More specifically, `recurrence` specifies coefficients `c` in the relation
    // `a[i] = c[0] * a[i - 1] + ... + c[n - 1] * a[i - n]`.
    // Returns `0` if `recurrence` and `init` are empty.
    // Requires `recurrence.size() == init.size()`.
    // Requires `k >= 0`.
    static mint solve_recurrence(const fps &recurrence, const fps &init, int64_t k) {
        assert(recurrence.size() == init.size());
        assert(k >= 0);
        int n = recurrence.size();
        if (n == 0) return 0;
        if (k < n) return init[k];
        fps denominator(n + 1, 1);
        for (int i = 0; i < n; i++) denominator[i + 1] = -recurrence[i];
        fps numerator = denominator * init;
        numerator.resize(n);
        return bostan_mori(numerator, denominator, k);
    }

    // Given a vector of pairs `{x_i, y_i}`, returns `f` such that `f(x_i) == y_i` for all `i`.
    // Requires `vec` to contain distinct `x_i`'s.
    static fps interpolate(const std::vector<std::pair<mint, mint>> &vec) {
        int m = vec.size(), len = 1;
        while (len < m) len *= 2;
        std::vector<fps> nodes(len * 2);
        for (int i = 0; i < m; i++) nodes[i + len] = {-vec[i].first, 1};
        for (int i = m; i < len; i++) nodes[i + len] = {1};
        for (int i = len - 1; i > 0; i--) nodes[i] = nodes[i * 2] * nodes[i * 2 + 1];
        auto solve = [&](auto &solve, int i, fps poly) -> fps {
            if (i >= len + m) return {};
            poly %= nodes[i];
            if (i >= len) {
                assert(poly[0] != 0);
                return {vec[i - len].second / poly[0]};
            }
            return solve(solve, i * 2, poly) * nodes[i * 2 + 1] + solve(solve, i * 2 + 1, poly) * nodes[i * 2];
        };
        return solve(solve, 1, fps::derivative(nodes[1]));
    }

    // Given `f(x)`, returns `f(y)` where `y == x + offset`.
    static fps taylor_shift(const fps &f, mint offset) {
        int len = f.size();
        fps result(len, 1), p(len), q(len);
        for (int i = 2, p = mint::mod(); i < len; i++) {
            result[i] = p / i * -result[p % i];
        }
        for (int i = 1; i < len; i++) result[i] *= result[i - 1];
        mint acc = 1;
        for (int i = 0; i < len; i++) {
            p[len - 1 - i] = f[i] * acc;
            acc *= i + 1;
        }
        acc = 1;
        for (int i = 0; i < len; i++) {
            q[i] = result[i] * acc;
            acc *= offset;
        }
        fps r = p * q;
        for (int i = 0; i < len; i++) result[i] *= r[len - 1 - i];
        return result;
    }
};

}  // namespace kotone

#endif  // KOTONE_FORMAL_POWER_SERIES_HPP
// #include <kotone/modint_utility>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_MODINT_UTILITY_HPP
#define KOTONE_MODINT_UTILITY_HPP 1

#include <vector>
#include <cassert>
// #include <kotone/internal_type_traits>
// https://github.com/amiast/cpp-utility


namespace kotone {

// Returns a length-`(n+1)` vector `reciprocal` such that `reciprocal[i]` is the modular inverse of `i`.
// The value of `reciprocal[0]` is undefined.
// Requires `mint::mod()` to be prime.
// Requires `1 <= n < mint::mod()`.
template <compatible_modint mint> std::vector<mint> reciprocals(int n) {
    int p = mint::mod();
    assert(1 <= n && n <= p);
    std::vector<mint> result(n + 1);
    result[1] = 1;
    for (int i = 2; i <= n; i++) {
        result[i] = -(p / i) * result[p % i];
    }
    return result;
}

// Returns a vector containing the first `n + 1` factorials (`0!, 1!, ..., n!`).
// Requires `n >= 0`.
template <compatible_modint mint> std::vector<mint> factorials(int n) {
    assert(n >= 0);
    std::vector<mint> result(n + 1);
    result[0] = 1;
    for (int i = 1; i <= n; i++) result[i] = i * result[i - 1];
    return result;
}

// Returns a vector of inverse factorials given the vector of factorials.
// Requires `vec_factorial` to match the format of the output of `factorials()`.
// Requires `mint::mod()` to be prime.
// Requires `1 <= vec_factorial.size() <= mint::mod()`.
template <compatible_modint mint> std::vector<mint> inv_factorials(const std::vector<mint> &vec_factorial) {
    int len = vec_factorial.size();
    int p = mint::mod();
    assert(1 <= len && len <= p);
    std::vector<mint> result(len);
    assert(vec_factorial[len - 1] != 0);
    result[len - 1] = vec_factorial[len - 1].inv();
    for (int i = len - 1; i > 0; i--) result[i - 1] = i * result[i];
    return result;
}

// A wrapper class for combinatorial functions with modint.
template <compatible_modint mint> struct modint_utility {
  private:
    std::vector<mint> _inv, _fact, _ifact;
    int _p = -1, _max_n = -1;

    void _build(int new_max) {
        if (new_max <= _max_n) return;
        _inv.resize(new_max + 1, 1);
        _fact.resize(new_max + 1, 1);
        _ifact.resize(new_max + 1, 1);
        for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) {
            _inv[i] = -(_p / i) * _inv[_p % i];
        }
        for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) _fact[i] = i * _fact[i - 1];
        for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) _ifact[i] = _inv[i] * _ifact[i - 1];
        _max_n = new_max;
    }

  public:
    modint_utility() : _p(mint::mod()) {}

    // Instantiates with the first `n + 1` factorials (`0!, 1!, ..., n!`) precomputed.
    // Requires `mint::mod()` to be prime.
    // Requires `mint::mod()` to be invariant.
    // Requires `n < mint::mod()`.
    modint_utility(int n) {
        _p = mint::mod();
        assert(n < _p);
        _build(n);
    }

    // Returns the modular inverse of `n`.
    // Requires `1 <= n < mint::mod()`.
    mint inv(int n) {
        assert(1 <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _inv[n];
    }

    // Returns `n!`.
    // Requires `0 <= n < mint::mod()`.
    mint factorial(int n) {
        assert(0 <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _fact[n];
    }

    // Returns the modular inverse of `n!`.
    // Requires `0 <= n < mint::mod()`.
    mint inv_factorial(int n) {
        assert(0 <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _ifact[n];
    }

    // Returns the number of permutations of `k` of `n` objects.
    // Requires `0 <= k <= n < mint::mod()`.
    mint perm(int n, int k) {
        assert(0 <= k && k <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _fact[n] * _ifact[n - k];
    }

    // Returns the number of combinations of `k` of `n` objects.
    // Requires `0 <= k <= n < mint::mod()`.
    mint comb(int n, int k) {
        assert(0 <= k && k <= n && n < _p);
        if (n >= _max_n) _build(n);
        return _fact[n] * _ifact[k] * _ifact[n - k];
    }

    // Returns the `n`-th Catalan number.
    // Requires `0 <= n * 2 < _p`.
    mint catalan(int n) {
        assert(0 <= n && n * 2 < _p);
        if (n * 2 >= _max_n) _build(n * 2);
        return _fact[n * 2] * _ifact[n + 1] * _ifact[n];
    }
};

// Returns a square root of the given value.
// If no square root exists, returns `0`.
// If there are multiple square roots, the function may return any of them.
template <compatible_modint mint> mint sqrt_mint(mint val) {
    if (val == 0) return 0;
    int mod = mint::mod();
    if (mod == 2) return val;
    if (val.pow((mod - 1) / 2) == -1) return 0;
    if (mod % 4 == 3) return val.pow((mod + 1) / 4);

    int s = 0;
    int q = mod - 1;
    while (q % 2 == 0) {
        q /= 2;
        s++;
    }

    mint z = 2;
    while (z.pow((mod - 1) / 2) == 1) z++;
    mint c = z.pow(q);
    mint x = val.pow((q + 1) / 2);
    mint t = val.pow(q);

    while (t != 1) {
        int i = 0;
        mint tpow = t;
        while (tpow != 1 && i < s) {
            tpow *= tpow;
            i++;
        }
        if (i == s) return 0;
        mint b = c.pow(1 << (s - i - 1));
        x *= b;
        t *= b * b;
        c = b * b;
        s = i;
    }
    return x;
}

}  // namespace kotone

#endif  // KOTONE_MODINT_UTILITY_HPP

using mint = atcoder::modint998244353;
using fps = kotone::formal_power_series<mint>;

int main() {
    int N;
    std::cin >> N;
    kotone::modint_utility<mint> util(N);
    fps f(N);
    for (int i = 0; i < N; i++) f[i] = util.inv_factorial(i) * (i + 1);
    mint result = fps::power(f, N, N - 1)[N - 2];
    result *= util.factorial(N - 2);
    result /= mint(N).pow(N - 2);
    std::cout << result.val() << std::endl;
}