AT_abc323_g [ABC323G] Inversion of Tree

题目描述

给定一个长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，其中 $P$ 是 $1$ 到 $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$。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出 $N$ 个用空格隔开的整数，第 $K$ 个数表示满足条件的树的个数对 $998244353$ 取模的结果，$K=0,1,\ldots,N-1$。

输入输出样例 #1

输入 #1

3
1 3 2

输出 #1

1 2 0

输入输出样例 #2

输入 #2

10
3 1 4 10 8 6 9 2 7 5

输出 #2

294448 2989776 12112684 25422152 30002820 20184912 7484084 1397576 108908 2640

说明/提示

限制条件

• $2\leq N\leq 500$
• $P$ 是 $1$ 到 $N$ 的一个排列

样例解释 1

当 $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$。

由 ChatGPT 4.1 翻译