← 返回题目列表

AtCoder · arc167_f

F. 树树树

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

给你整数 N 和 K 这样 2\leq K\leq N.

问题:土豆

我们有一棵加权有根树 N 顶点编号 1 to N。顶点 1 是根。

对于每个 2\leq i\leq N,顶点的父级 i is p_{i}\;(1\leq p_{i}<i),以及边缘连接 i 和 p_{i} 的重量为 q_{i-1}.

在这里, q=(q_{1},q_{2},\dots,q_{N-1}) 是一个排列 (1,2,\dots,N-1).

让 cost(u,v) 是连接顶点的简单路径中边的最大权重 u 和 v.

查找 \sum_{u=1}^{N} \sum_{v=u+1}^{N} cost(u,v).


问题:番茄

给你一个整数 a 这样 1\leq a\lt K。有 \frac{((N-1)!)^{2}}{K-1} 可能的对 p 和 q 在问题“土豆”中,这样 p_{K}=a。求总和,取模 998244353,所有这些对的问题的答案。

对于每个 a=1,\dots,K-1,找到问题“番茄”的答案。

约束

  • 2\leq K\leq N\leq 10^{5}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K

输出

打印 K-1 行。的 i-th 行应包含问题“tomato”的答案 a=i.


示例输入 1

4 4

示例输出 1

170
170
172

示例输入 2

3 2

示例输出 2

20

示例输入 3

16 7

示例输出 3

457991130
457991130
65525944
418314090
644126049
676086428