[2017国家集训队测试]生成树计数

内存限制：512 MiB 时间限制：100 Sec

在一个s个点的图中，存在s-n条边，使图中形成了n个连通块，第i个连通块中有ai

个点。现在我们需要再连接n?1条边，使该图变成一棵树。对一种连边方案，设原图中第i个连通块连出了di条边，那么这棵树T的价值为：

你的任务是求出所有可能的生成树的价值之和，对998244353取模。

输入的第一行包含两个整数n,m意义见题目描述。

接下来一行有n个整数，第i个整数表示ai(1≤ai<998244353)

你可以由ai计算出图的总点数s，所以在输入中不再给出s的值。

本题共有 20个测试点，每个测试点 5 分。

20%的数据中，n≤500

另外 20% 的数据中，n≤3000

另外 10% 的数据中，n≤10010,m=1

另外 10%的数据中，n≤10015,m=2

另外 20% 的数据中，所有 ai相等。

100% 的数据中，n≤3×10^4,m≤30

输出包含一行一个整数，表示答案。


			3 1

2 3 4


			1728

样例解释1

令i表示大小为i的原连通块，我们在连通块之间的连边有以下三种可能:

2−3−4

3−2−4

2−4−3

价值和为:

(2×3^2×4×2+3×2^2×4×2+2×4^2×3×2)×(1+2+1)=1728

测评似乎有问题，请自行下数据测JudgeOnline/upload/201801/5119.rar

BZPRO Powered by Remmina.
Github Repository

#5119. [2017国家集训队测试]生成树计数