103037: [Atcoder]ABC303 Ex - Constrained Tree Degree

Problem Statement

You are given an integer $N$ and a set $S=\lbrace S_1,S_2,\ldots,S_K\rbrace$ consisting of integers between $1$ and $N-1$.

Find the number, modulo $998244353$, of trees $T$ with $N$ vertices numbered $1$ through $N$ such that:

• $d_i\in S$ for all $i\ (1\leq i \leq N)$, where $d_i$ is the degree of vertex $i$ in $T$.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the number, modulo $998244353$, of the conforming trees $T$.

Sample Input 1

4 2
1 3

Sample Output 1

4

A tree satisfies the condition if the degree of one vertex is $3$ and the others' are $1$. Thus, the answer is $4$.

Sample Input 2

10 5
1 2 3 5 6

Sample Output 2

68521950

Sample Input 3

100 5
1 2 3 14 15

Sample Output 3

888770956

Print the count modulo $998244353$.

问题描述

给你一个整数$N$和一个由$1$到$N-1$的整数组成的集合$S=\lbrace S_1,S_2,\ldots,S_K\rbrace$。

找到满足以下条件的树$T$的数量（对$998244353$取模）：

• 对于所有$i\ (1\leq i \leq N)$，$d_i\in S$，其中$d_i$是树$T$中顶点$i$的度数。

限制条件

• $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$
• 输入中的所有值都是整数。

输入

输入通过标准输入以以下格式给出：

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

输出

打印满足条件的树$T$的数量（对$998244353$取模）。

样例输入1

4 2
1 3

样例输出1

4

如果一个树中一个顶点的度数为$3$，其余顶点的度数为$1$，则该树满足条件。 因此，答案是$4$。

样例输入2

10 5
1 2 3 5 6

样例输出2

68521950

样例输入3

100 5
1 2 3 14 15

样例输出3

888770956

打印对$998244353$取模后的计数。