← 返回题目列表

AtCoder · stpc2025_1_j

J. 划分多边形

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

配点 : 100 点

問題文

正整数 N 的大小 M 的整数集合 关于 S = \lbrace S_{1}, S_{2}, \dots , S_{M} \rbrace 。 如果输入

k = 0, 1, \dots , N - 3 ,请回答以下问题。

在顶点上 1, 2, \dots, N 编号的正 N 多边形中,k 条对角线以不在顶点处互相相交的方式画出。 此时,由对角线形成的正 N 多边形是 k + 1 个多边形被分割。这些分割的多边形的边数分别 e_{1}, e_{2}, \dots, e_{k + 1} 。

在这里,k 条对角线的画法良好的画法是指满足以下条件。

  • e_{1}, e_{2}, \dots ,e_{k + 1} 全部 S 包含在内。

k 条对角线的良好的画法的数量 998244353 取余。起初,数列

制約

  • 输入全部为整数
  • 3\leq N\leq 10^{5}
  • 1\leq M\leq N - 2
  • 3\leq S_{i}\leq N
  • S_{i} < S_{i + 1}

入力

输入按以下格式给出。

N M
S_{1} S_{2} \dots S_{M}

出力

N - 2 行。i = 1, 2, \dots, N - 2 来说,i 在线 k = i - 1 当 时输出答案。


入力例 1

5 2
3 4

出力例 1

0
5
5

k = 0 时,总是 e_{1} = 5 。5 是 给出了 S 中,答案是 0 。

k = 1 时,总是 \{e_{1}, e_{2}\} = \{3, 4\} ,两者都包含在 S 中。正 5 形的对角线 1 由于存在本抽取方法的 5 种方式,因此答案是 5 。

k = 2 时,总是 e_{i} = 3 \;(1\leq i\leq 3) 。正 5 多边形中画对角线时不相交 2 由于存在本抽取方法的 5 种方式,因此答案是 5 。


入力例 2

4 1
4

出力例 2

1
0

入力例 3

16 7
3 4 6 7 9 12 16

出力例 3

1
24
544
14280
120156
829464
3372120
10914816
24515700
40532624
52300160
42493880
17383860
2674440