#2320. 「清华集训 2017」生成树计数

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

题目描述

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

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

\mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right)

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

输入格式

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

接下来一行有 n 个整数,第 i 个整数表示 a_i (1\le a_i< 998244353)

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

输出格式

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

样例

样例输入 1

3 1
2 3 4

样例输出 1

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

样例 2

见附加文件

数据范围与提示

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

  • 20\% 的数据中, n\le500

  • 另外 20\% 的数据中, n \le 3000

  • 另外 10\% 的数据中, n \le 10010, m = 1

  • 另外 10\% 的数据中, n \le 10015,m = 2

  • 另外 20\% 的数据中,所有 a_i 相等。

  • 100\% 的数据中, n \le 3\times 10^4,m \le 30

其中,每一个部分分的测试点均有一定梯度。