#6363. 「地底蔷薇」

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

由于内部原因，题目背景没了。

给定集合 $S$ ，请你求出 $n$ 个点的「所有极大点双连通分量的大小都在 $S$ 内」的不同简单无向连通图的个数对 $998244353$ 取模的结果。

点双连通分量：删去任意一个点后剩下的点依然保持连通的连通子图。
极大点双连通分量：一个点双连通分量，且不存在更大的点双连通分量包含自己。
极大点双连通分量的大小：指连通分量包含的点数。
两个简单无向图不同，当且仅当存在某条边 $(u,v)$ 出现在了其中一个无向图，而没有出现在另一个无向图。

第一行包含两个整数 $n,|S|$ ，表示图的点数以及集合 $S$ 的大小。
第二行包含 $|S|$ 个整数，表示集合 $S$ 的元素。

包含一个整数，表示答案对 $998244353$ 取模的结果。

输入

5 1
2

输出

$S=\{2\}$ ，可以证明这等价于图中不存在环。5 个点的有标号无根树共有 $5^3=125$ 种。

对于10%的数据， $n\leq6$ 。
对于30%的数据， $n\leq12$ 。
对于50%的数据， $n\leq1000$ 。
对于100%的数据， $n\leq10^5,(\sum_{x\in S}x)\leq10^5$ 。

题目来源：全是水题的 GD 省选模拟赛 by zjt