分数: 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