103037: [Atcoder]ABC303 Ex - Constrained Tree Degree
Description
Score : $600$ points
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$.
Input
题意翻译
给定一个长度为 $K$ 的正整数序列 $S$,求有多少个不同的树 $T$ 使得: * $T$ 中有 $N$ 个节点。 * 对于 $T$ 中的任意一个节点 $i$ 的度数 $d_i$,有 $d_i\in S$。Output
分数:600分
问题描述
给你一个整数$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$取模后的计数。