結果

問題 No.3443 Sum of (Tree Distances)^K 1
コンテスト
ユーザー risujiroh
提出日時 2026-02-06 23:05:22
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 6,993 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,042 ms
コンパイル使用メモリ 365,852 KB
実行使用メモリ 15,108 KB
最終ジャッジ日時 2026-02-06 23:05:34
合計ジャッジ時間 11,084 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using Mint = atcoder::modint998244353;

Comb<Mint> comb;

void Solve() {
  int n, k;
  IN(n, k);

  vector<Mint> a(n + 1);
  for (int m : Rep1(2, n)) {
    a[m] = Mint(n).pow(n - m) * comb.Fact(n) * comb.Inv(2) * comb.FactInv(n - m);
    a[m - 1] -= a[m];
  }

  vector<Mint> fj(n);
  for (int j : Rep(0, n)) {
    fj[j] = comb.FactInv(j) * comb.BinomInv(n, j + 1) * a[j + 1] * Mint(j).pow(k);
  }

  vector<Mint> ans(n);

  vector<Mint> inv(n);
  for (int i : Rep(0, n)) {
    inv[i] = comb.FactInv(i);
  }

  ans = atcoder::convolution(inv, fj);
  ans.resize(n);

  for (int i : Rep(0, n)) {
    // for (int j : Rep1(0, i)) {
    //   ans[i] += comb.FactInv(i - j) * fj[j];
    // }
    ans[i] *= comb.Fact(i);
  }

  ranges::for_each(ans, LIFT(OUT));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

#include <atcoder/convolution.hpp>
#include <atcoder/modint.hpp>

template <class T>
class Comb {
 public:
  Comb() = default;

  explicit Comb(int n) {
    Reserve(n);
  }

  void Reserve(int n) {
    const int sz = static_cast<int>(fact_.size());
    if (n < sz) {
      return;
    }
    fact_.resize(n + 1);
    const int nsz = static_cast<int>(fact_.capacity());
    fact_.resize(nsz);
    fact_inv_.resize(nsz);
    for (int i = sz; i < nsz; ++i) {
      fact_[i] = T(i) * fact_[i - 1];
    }
    fact_inv_.back() = T(1) / fact_.back();
    for (int i = nsz; --i > sz;) {
      fact_inv_[i - 1] = fact_inv_[i] * T(i);
    }
  }

  T Fact(int n) {
    assert(n >= 0);
    Reserve(n);
    return fact_[n];
  }

  T FactInv(int n) {
    if (n < 0) {
      return T(0);
    }
    Reserve(n);
    return fact_inv_[n];
  }

  T FactRatio(int a, int b) {
    if (a >= 0) {
      return Fact(a) * FactInv(b);
    }
    assert(b < 0);
    const T t = FactRatio(~b, ~a);
    return (a - b) % 2 == 0 ? t : -t;
  }

  T Inv(int n) {
    assert(n != 0);
    return FactRatio(n - 1, n);
  }

  T Prod(std::ranges::iota_view<int, int> r) {
    return FactRatio(r.end()[-1], r[-1]);
  }

  T ProdInv(std::ranges::iota_view<int, int> r) {
    assert(r[0] > 0 || r.end()[-1] < 0);
    return FactRatio(r[-1], r.end()[-1]);
  }

  T Perm(int n, int k) {
    assert(n >= 0 ? true : k > n);
    return FactRatio(n, n - k);
  }

  T PermInv(int n, int k) {
    assert(n >= 0 ? k <= n : true);
    return FactRatio(n - k, n);
  }

  T Binom(int n, int k) {
    k = std::max(k, n - k);
    return Perm(n, k) * FactInv(k);
  }

  T BinomInv(int n, int k) {
    assert(n >= 0 ? 0 <= k && k <= n : 0 <= k || k <= n);
    k = std::max(k, n - k);
    return PermInv(n, k) * Fact(k);
  }

  T Multinom(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    T ret = FactRatio(n, min_k);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= FactInv(k);
      }
    }
    return ret;
  }

  template <class... Ks>
  requires(...&& std::same_as<Ks, int>)
      T Multinom(Ks... ks) {
    return Multinom(std::initializer_list<int>{ks...});
  }

  T MultinomInv(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    assert(n >= 0 ? min_k >= 0
                  : std::ranges::all_of(ks, [&](auto& k) { return &k == &min_k || k >= 0; }));
    T ret = FactRatio(min_k, n);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= Fact(k);
      }
    }
    return ret;
  }

  template <class... Ks>
  requires(...&& std::same_as<Ks, int>)
      T MultinomInv(Ks... ks) {
    return MultinomInv(std::initializer_list<int>{ks...});
  }

  T Homogeneous(int n, int k) {
    return Binom(n + k - 1, k);
  }

  T Catalan(int n) {
    assert(n >= 0);
    return Fact(2 * n) * FactInv(n) * FactInv(n + 1);
  }

  T Catalan(int n, int k) {
    assert(0 <= k && k <= n);
    return T(n - k + 1) * Fact(n + k) * FactInv(n + 1) * FactInv(k);
  }

 private:
  std::vector<T> fact_{T(1)};
  std::vector<T> fact_inv_{T(1)};
};

template <class T>
concept MyRange =
    std::ranges::range<T> &&
    !std::convertible_to<T, std::string_view> &&
    !std::convertible_to<T, std::filesystem::path>;

template <class T>
concept MyTuple = std::__is_tuple_like<T>::value && !MyRange<T>;

namespace std {

istream& operator>>(istream& is, MyRange auto&& r) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

istream& operator>>(istream& is, MyTuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, MyRange auto&& r) {
  auto sep = "";
  for (auto&& e : r) {
    os << exchange(sep, " ") << forward<decltype(e)>(e);
  }
  return os;
}

ostream& operator<<(ostream& os, MyTuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
istream& operator>>(istream& is, T& x) {
  int v;
  is >> v;
  x = T::raw(v);
  return is;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
ostream& operator<<(ostream& os, const T& x) {
  return os << x.val();
}

}  // namespace std

template <class T>
class OneBased {
 public:
  explicit OneBased(T&& x) : ref_(std::forward<T>(x)) {}

  template <class... Ts>
  requires(sizeof...(Ts) > 1)
      OneBased(Ts&&... xs) : ref_(std::forward_as_tuple(std::forward<Ts>(xs)...)) {}

  friend std::istream& operator>>(std::istream& is, OneBased x) {
    if constexpr (MyRange<T>) {
      for (auto&& e : x.ref_) {
        is >> ::OneBased(e);
      }
    } else if constexpr (MyTuple<T>) {
      std::apply([&](auto&... xs) { (is >> ... >> ::OneBased(xs)); }, x.ref_);
    } else {
      is >> x.ref_;
      --x.ref_;
    }
    return is;
  }

  friend std::ostream& operator<<(std::ostream& os, OneBased x) {
    if constexpr (MyRange<T>) {
      auto f = [](auto&& e) { return ::OneBased(std::forward<decltype(e)>(e)); };
      os << (x.ref_ | std::views::transform(f));
    } else if constexpr (MyTuple<T>) {
      std::apply([&](auto&... xs) { os << std::tuple(::OneBased(xs)...); }, x.ref_);
    } else {
      os << ++x.ref_;
      --x.ref_;
    }
    return os;
  }

 private:
  T ref_;
};

template <class T>
OneBased(T&&) -> OneBased<T>;

template <class... Ts>
OneBased(Ts&&...) -> OneBased<std::tuple<Ts...>>;

using namespace std;

#define LIFT(f) ([&](auto&&... xs) -> decltype(auto) { return f(forward<decltype(xs)>(xs)...); })
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Rep1(...) [](int l, int r) { return Rep(l, r + 1); }(__VA_ARGS__)
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1
0