AT_abc303_h [ABC303Ex] Constrained Tree Degree

题目描述

给定一个整数 $N$，以及一个由 $1$ 到 $N-1$ 之间的整数构成的集合 $S=\lbrace S_1, S_2, \ldots, S_K \rbrace$。

请计算满足以下条件的 $N$ 个顶点的树 $T$（顶点编号为 $1$ 到 $N$）的个数，并输出其对 $998244353$ 取模的结果。

• 对于任意 $i\ (1\leq i \leq N)$，设 $T$ 中顶点 $i$ 的度数为 $d_i$，则 $d_i \in S$。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $S_1$ $S_2$ $\ldots$ $S_K$

输出格式

输出满足条件的树 $T$ 的个数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

4 2
1 3

输出 #1

4

输入输出样例 #2

输入 #2

10 5
1 2 3 5 6

输出 #2

68521950

输入输出样例 #3

输入 #3

100 5
1 2 3 14 15

输出 #3

888770956

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq N-1$
• $1 \leq S_1 < S_2 < \ldots < S_K \leq N-1$
• 所有输入均为整数

样例解释 1

存在一种情况，其中一个顶点的度数为 $3$，其余顶点的度数均为 $1$，这样的树满足条件。因此答案为 $4$ 个。

样例解释 3

请输出个数对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译