問題一覧 > 通常問題

No.3443 Sum of (Tree Distances)^K 1

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : 👑 potato167 / テスター : noya2
ProblemId : 12981 / yukicoder contest 492 (順位表) / 自分の提出
問題文最終更新日: 2026-02-05 18:12:58
yukicoder contest 492の他の問題:

問題文

正整数 $N, K$ が与えられます。

$a = 1, 2, \dots, N$ に対して、以下の問いの答えを求めてください。

頂点に $1, 2, \dots, N$ の番号がついた $N$ 頂点の木のスコアを以下のように定義します。

  • $1\leq u < v\leq N$ かつ頂点 $u, v$ 間のパスに含まれる頂点の中の頂点番号の最大値が $a$ であるような全ての整数組 $(u, v)$ に対する、$\mathrm{dist}(u, v)^{K}$ の総和

ここで、$\mathrm{dist}(u, v)$ は頂点 $u, v$ 間にある辺の数とします。

$N$ 頂点の木 $N^{N - 2}$ 通り全てに対する木のスコアの総和を $998244353$ で割ったあまりを求めてください。

制約

  • $2\leq N\leq 2\times 10^{5}$
  • $1\leq K\leq 2\times 10^{5}$
  • 入力は全て整数

入力

$N\ K$

出力

$N$ 行出力してください。

$i$ 行目には $a = i$ であるときの答えを出力してください。

サンプル

サンプル1
入力
3 1
出力
0
2
10

$a = 3$ について、 頂点数 $3$ の木は $3$ 通りあります。 まず、以下の木の場合を考えます。

  • 辺が $(1, 3), (2, 3)$ である木

このとき、任意の相異なる頂点間のパス上の頂点番号の最大値が $3$ となります。また、$\mathrm{dist}(1, 2) + \mathrm{dist}(1, 3) + \mathrm{dist}(2, 3) = 4$ です。

そのほか $2$ つの木は以下の $2$ 通りです。

  • 辺が $(1, 2), (2, 3)$ である木
  • 辺が $(1, 2), (1, 3)$ である木

いずれの木でも、パス上の頂点番号の最大値が $3$ となる組は $(1,3),(2,3)$ の $2$ 組であり、$\mathrm{dist}(1, 3) + \mathrm{dist}(2, 3) = 3$ です。

よって、$3$ 行目には $4 + 3 + 3 = 10$ を出力します。

サンプル2
入力
4 2
出力
0
8
52
240
サンプル3
入力
16 7
出力
0
527847872
93332076
109615847
258637013
539343718
625376669
686676298
773193610
111668573
42127766
367068509
472315096
626321962
49032390
557093458

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。