Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Cho một số nguyên dương $N$ và một tập hợp các số nguyên $S = \{S_1, S_2, \dots, S_M\}$ có kích thước $M$.

Với mỗi $k = 0, 1, \dots, N - 3$, hãy trả lời câu hỏi sau:

Xét một đa giác đều $N$ cạnh có các đỉnh được đánh số $1, 2, \dots, N$. Vẽ đúng $k$ đường chéo sao cho không có hai đường chéo nào cắt nhau ngoại trừ có thể tại các đầu mút của chúng. Kết quả là đa giác đều $N$ cạnh được chia thành $k + 1$ đa giác. Gọi $e_1, e_2, \dots, e_{k+1}$ là số cạnh của các đa giác thu được này.

Ta nói một cách vẽ $k$ đường chéo là một cách tốt nếu nó thỏa mãn điều kiện sau:

  • Tất cả $e_1, e_2, \dots, e_{k+1}$ đều nằm trong tập hợp $S$.

Hãy tính số cách tốt để vẽ $k$ đường chéo, chia lấy dư cho $998244353$.

Dữ liệu vào

Dữ liệu vào được cho dưới định dạng sau:

N M
S1 S2 ... SM
  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $3 \le N \le 10^5$
  • $1 \le M \le N - 2$
  • $3 \le S_i \le N$
  • $S_i < S_{i+1}$

Kết quả

In ra $N - 2$ dòng. Với $i = 1, 2, \dots, N - 2$, in ra trên dòng thứ $i$ câu trả lời tương ứng với $k = i - 1$.

Ví dụ

Dữ liệu vào mẫu 1

5 2
3 4

Kết quả mẫu 1

0
5
5

Dữ liệu vào mẫu 2

4 1
4

Kết quả mẫu 2

1
0

Dữ liệu vào mẫu 3

16 7
3 4 6 7 9 12 16

Kết quả mẫu 3

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

Ghi chú

Trong ví dụ đầu tiên, khi $k = 0$, ta luôn có $e_1 = 5$. Vì $5$ không nằm trong $S$, nên câu trả lời là $0$.

Khi $k = 1$, ta luôn có $\{e_1, e_2\} = \{3, 4\}$, và cả hai giá trị này đều nằm trong $S$. Có $5$ cách để vẽ một đường chéo trong một ngũ giác đều, vì vậy câu trả lời là $5$.

Khi $k = 2$, ta luôn có $e_i = 3$ ($1 \le i \le 3$). Có $5$ cách để vẽ hai đường chéo không cắt nhau trong một ngũ giác đều, vì vậy câu trả lời là $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.