#6363. 「地底蔷薇」

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ez_zjt

题目描述

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

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

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

输入格式

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

输出格式

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

样例

样例输入

5 1
2

样例输出

125

样例解释

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