103037: [Atcoder]ABC303 Ex - Constrained Tree Degree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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$取模后的计数。

加入题单

上一题 下一题 算法标签: