← 返回题目列表

AtCoder · utpc2020_d

D. 偶像团体服装

中文机器翻译题面 查看原题

問題文

N 作为多人组合偶像团体的制作人 Motsu-P,决定在其中 K 人中组建团体内的子组合。为了选出幸运的成员成为子组合成员, K 人的子组合成员将在演出前随机均匀选出。

偶像 i\ (1\leq i\leq N) 是 可以表示为 M_i 件服装 1,\ 2,\ldots,M_i 拥有。他们被告知在新子组合首秀演出中可以随意穿任何服装,因此她们会从各自拥有的服装中均匀随机地选择 1 来选择。然而现在我才意识到,组合的服装最好是统一的。但演出当天已经到了,现在更换服装已经来不及了。为了 Motsu-P 的心理安定,请计算组合服装恰巧统一的概率。

但是,只有当组合全员的服装号码相同时,才认为组合服装统一。并且所要求的概率可以证明是有理数,因此如注中所述,\bmod 998244353 输出。

出力方法
在输出有理数时,首先应将该有理数写成分数  \frac p q 。在这里,p, q 是一个整数并且q 是 您也可以写 998244353 不可被整除(在本问题的约束下,这种表示总是可能的)。然后, p\equiv qr\pmod{998244353}  输出有多少个 0 以上 998244353 小于的唯一整数 r 。 须满足
组合成员和服装的选取方法
组合成员以及各偶像选择衣服的方式,都是独立且均匀随机选择的。也就是说,组合成员是 {}_N C_K 选择方式的通路同样以相同的概率被选出。此外,独立于此的偶像 i 选择的服装 M_i 的选择方式通路同样以相同的概率被选出。

制約

  • 所有输入均为整数。
  • 1 \leq K \leq N \leq 10^5
  • 1 \leq M_i \leq 10^8\ (1\leq i\leq N)

部分点

  • 1 \leq N \leq 2000 的数据集 给出 50 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

N K
M_1 M_2 \ldots M_N

出力

答案 请打印除以 1 行输出。


入力例 1

3 2
1 2 3

出力例 1

55458020

将所选的偶像组合 (x,y) 表示出来时,组合服装一致的概率是 (1,2) 什么时候 \frac12, (1,3) 什么时候 \frac13 , (2,3) 什么时候 \frac13 ,所以整体上请注意以 \frac13\left(\frac12+\frac13+\frac13\right)=\frac7{18} 。 对于\bmod 998244353 回答。


入力例 2

10 5
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751

出力例 2

819006280