/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。
頂点に 1 から N の番号が付いた N 頂点の木のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを K=0,1,\ldots,N-1 に対して求めてください。
- 木で直接辺で結ばれた頂点の組 (u_i,v_i)\ (u_i < v_i) のうち、 P_{u_i}>P_{v_i} を満たすものがちょうど K 個ある。
制約
- 2\leq N\leq 500
- P は (1,2,\ldots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
各 K=0,1,\ldots,N-1 に対して、条件を満たす木の個数を 998244353 で割ったあまりを空白区切りで出力せよ。
入力例 1
3 1 3 2
出力例 1
1 2 0
K=0 のときの答えは、頂点 1,2 と頂点 1,3 を結ぶ木の一つです。実際、P_1 < P_2, P_1<P_3 です。
K=1 のときの答えは、頂点 1,2 と頂点 2,3 を結ぶ木と頂点 1,3 と頂点 2,3 を結ぶ木の二つです。実際、頂点 1,2 と頂点 2,3 を結ぶ木では、P_1 < P_2, P_2>P_3 です。
入力例 2
10 3 1 4 10 8 6 9 2 7 5
出力例 2
294448 2989776 12112684 25422152 30002820 20184912 7484084 1397576 108908 2640
Score : 650 points
Problem Statement
You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
For each K=0,1,\ldots,N-1, find the number, modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the following condition.
- Among the pairs of vertices (u_i,v_i)\ (u_i < v_i) that are directly connected by an edge in the tree, exactly K pairs satisfy P_{u_i}>P_{v_i}.
Constraints
- 2\leq N\leq 500
- P is a permutation of (1,2,\ldots,N).
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
For each K=0,1,\ldots,N-1, print the number, modulo 998244353, of trees that satisfy the condition, with spaces in between.
Sample Input 1
3 1 3 2
Sample Output 1
1 2 0
The answer for K=0 is 1: the tree with edges connecting vertices 1,2 and 1,3. Indeed, P_1 < P_2 and P_1<P_3.
The answer for K=1 is 2: the tree with edges connecting vertices 1,2 and 2,3, and another with edges connecting vertices 1,3 and 2,3. Indeed, in the tree with edges connecting vertices 1,2 and 2,3, we have P_1 < P_2, P_2>P_3.
Sample Input 2
10 3 1 4 10 8 6 9 2 7 5
Sample Output 2
294448 2989776 12112684 25422152 30002820 20184912 7484084 1397576 108908 2640