树的逆序数

题目描述

给定一个 $(1,2,\ldots,N)$ 的排列 $P=(P_1,P_2,\ldots,P_N)$。

对于每个 $K=0,1,\ldots,N-1$，求出满足以下条件的、顶点编号为 $1$ 到 $N$ 的树的数量，对 $998244353$ 取模。

在树中通过边直接相连的顶点对 $(u_i,v_i)\ (u_i \lt v_i)$ 里，恰好有 $K$ 对满足 $P_{u_i}\gt P_{v_i}$。

输入格式

输入按以下格式从标准输入给出：

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

输出格式

对于每个 $K=0,1,\ldots,N-1$，输出满足条件的树的数量（对 $998244353$ 取模），以空格分隔。

样例

3
1 3 2

1 2 0

$K=0$ 的答案是 $1$：由连接顶点 $1,2$ 和 $1,3$ 的边组成的树。此时有 $P_1 \lt P_2$ 且 $P_1\lt P_3$。

$K=1$ 的答案是 $2$：由连接顶点 $1,2$ 和 $2,3$ 的边组成的树，以及由连接顶点 $1,3$ 和 $2,3$ 的边组成的树。例如在由连接顶点 $1,2$ 和 $2,3$ 的边组成的树中，有 $P_1 \lt P_2$、$P_2\gt P_3$。

10
3 1 4 10 8 6 9 2 7 5

294448 2989776 12112684 25422152 30002820 20184912 7484084 1397576 108908 2640

数据范围

• $2\leq N\leq 500$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列。