/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
2\leq K\leq N を満たす整数 N,K が与えられます。
問題 potato
1 から N までの番号がついた頂点数 N の重み付き根付き木があります。頂点 1 が根です。
2\leq i\leq N に対して、頂点 i の親は 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) を求めてください。
問題 tomato
1\leq a\lt K を満たす整数 a が与えられます。「問題 potato」 の p,q として p_{K}=a を満たすものは \frac{((N-1)!)^{2}}{K-1} 通り考えられますが、その全てに対する「問題 potato」の答えの和を 998244353 で割ったあまりを求めてください。
a=1,\dots,K-1 について、「問題 tomato」の答えを求めてください。
制約
- 2\leq K\leq N\leq 10^{5}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N K
出力
K-1 行出力してください。i 行目には a=i としたときの「問題 tomato」の答えを出力してください。
入力例 1
4 4
出力例 1
170 170 172
入力例 2
3 2
出力例 2
20
入力例 3
16 7
出力例 3
457991130 457991130 65525944 418314090 644126049 676086428
Score : 1200 points
Problem Statement
You are given integers N and K such that 2\leq K\leq N.
Problem: potato
We have a weighted rooted tree with N vertices numbered 1 to N. Vertex 1 is the root.
For each 2\leq i\leq N, the parent of vertex i is p_{i}\;(1\leq p_{i}<i), and the edge connecting i and p_{i} has a weight of q_{i-1}.
Here, q=(q_{1},q_{2},\dots,q_{N-1}) is a permutation of (1,2,\dots,N-1).
Let cost(u,v) be the maximum weight of an edge in the simple path connecting vertices u and v.
Find \sum_{u=1}^{N} \sum_{v=u+1}^{N} cost(u,v).
Problem: tomato
You are given an integer a such that 1\leq a\lt K. There are \frac{((N-1)!)^{2}}{K-1} possible pairs of p and q in the problem "potato" such that p_{K}=a. Find the sum, modulo 998244353, of the answers to the problem over all those pairs.
For each a=1,\dots,K-1, find the answer to the problem "tomato".
Constraints
- 2\leq K\leq N\leq 10^{5}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print K-1 lines. The i-th line should contain the answer to the problem "tomato" for a=i.
Sample Input 1
4 4
Sample Output 1
170 170 172
Sample Input 2
3 2
Sample Output 2
20
Sample Input 3
16 7
Sample Output 3
457991130 457991130 65525944 418314090 644126049 676086428