問題一覧 > 通常問題

No.3445 Sum of (Tree Distances)^K 2

レベル : / AI推定難易度 : 3025 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 6
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 12982 / 自分の提出
問題文最終更新日: 2026-02-05 18:12:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 492 (順位表) の他の問題:

Problem Statement

You are given positive integers $N, K$.

For each of $a = 1, 2, \dots, N$, solve the following problem.

Define the score of a tree with $N$ vertices numbered $1, 2, \dots, N$ as follows.

  • The sum of $\mathrm{dist}(u, v)^{K}$ over all integer pairs $(u, v)$ such that $1\leq u < v\leq N$ and the maximum vertex number among the vertices on the path between vertices $u, v$ is $a$

Here, $\mathrm{dist}(u, v)$ is the number of edges between vertices $u, v$.

Also, define a good tree with $N$ vertices as one satisfying the following condition.

  • Every vertex other than vertex $1$ has at least one adjacent vertex with a number smaller than its own.

Find the sum of the scores over all $(N - 1)!$ good trees with $N$ vertices, modulo $998244353$.

Constraints

  • $2\leq N\leq 2\times 10^{5}$
  • $1\leq K\leq 2\times 10^{5}$
  • All input values are integers.

Input

$N\ K$

Output

Output $N$ lines.

On the $i$-th line, output the answer for $a = i$.

Sample

Sample 1
Input
3 1
Output
0
2
6

Consider $a = 3$. There are the following $2$ good trees with $3$ vertices.

  • The tree with edges $(1, 2), (2, 3)$
  • The tree with edges $(1, 2), (1, 3)$

In either tree, the pairs for which the maximum vertex number on the path is $3$ are the $2$ pairs $(1,3),(2,3)$, and $\mathrm{dist}(1, 3) + \mathrm{dist}(2, 3) = 3$. Therefore, output $3 + 3 = 6$ on the $3$rd line.

Sample 2
Input
4 2
Output
0
6
30
74
Sample 3
Input
16 7
Output
0
972509923
673235942
320468187
122611210
963537619
521784234
840111140
813250073
737360429
805790705
758873901
731500670
364014601
274620614
615217237

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