Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

正の整数 $N$ と、要素数 $M$ の整数の集合 $S = \{S_1, S_2, \dots, S_M\}$ が与えられます。

各 $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$ で割った余りを求めてください。

入力

入力は以下の形式で与えられます:

N M
S1 S2 ... SM
  • 入力される値はすべて整数である。
  • $3 \le N \le 10^5$
  • $1 \le M \le N - 2$
  • $3 \le S_i \le N$
  • $S_i < S_{i+1}$

出力

$N - 2$ 行出力してください。$i = 1, 2, \dots, N - 2$ について、$i$ 行目に $k = i - 1$ に対応する答えを出力してください。

入出力例

入力例 1

5 2
3 4

出力例 1

0
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

ノート

最初の例では、$k = 0$ のとき常に $e_1 = 5$ となります。$5$ は $S$ に含まれないため、答えは $0$ です。

$k = 1$ のとき常に $\{e_1, e_2\} = \{3, 4\}$ となり、どちらの値も $S$ に含まれます。正五角形に対角線を一本引く方法は $5$ 通りあるため、答えは $5$ です。

$k = 2$ のとき常に $e_i = 3$($1 \le i \le 3$)となります。正五角形に交わらない二本の対角線を引く方法は $5$ 通りあるため、答えは $5$ です。

problem_16235_1.png

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.