← 返回题目列表

AtCoder · abc323_g

G. 树的反转

中文机器翻译题面 查看原题

分数: 650 点

问题陈述

给你一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

对于每个 K=0,1,\ldots,N-1,求模数 998244353,树木 N 顶点编号 1 to N 满足以下条件。

  • 在顶点对之间 (u_i,v_i)\ (u_i < v_i) 由树中的边直接连接,恰好 K 对满足 P_{u_i}>P_{v_i}.

约束

  • 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 is 1:具有连接顶点的边的树 1,2 和 1,3。确实, P_1 < P_2 和 P_1<P_3.

的答案 K=1 is 2:具有连接顶点的边的树 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