F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5119. -- [2017国家集训队测试]生成树计数

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

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 56  Solved: 3
[Submit][Status][Discuss]

Description

在一个s个点的图中,存在s-n条边,使图中形成了n个连通块,第i个连通块中有ai
个点。现在我们需要再连接n?1条边,使该图变成一棵树。对一种连边方案,设原图中第i个连通块连出了di条边,那么这棵树T的价值为:
 
你的任务是求出所有可能的生成树的价值之和,对998244353取模。

Input

输入的第一行包含两个整数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

Output

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

Sample Input

3 1
2 3 4

Sample Output

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

HINT

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

Source

[Submit][Status][Discuss]

HOME Back