← 返回题目列表

AtCoder · past202203_j

J. 预期范围

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

分数: 6 点

问题陈述

来自 N 整数 A_1,A_2,\ldots,A_N,我们会选择 K 不同的整数。在这里,任意组合 以相等的概率选择整数的 K 。

让 X 和 Y 分别是所选整数中的最大值和最小值。求出期望值 X-Y,模数 998244353.

注释

在本问题的约束下,可以证明所求的期望值可以表示为 p/q 使用两个互质整数 p,q,并且唯一存在一个整数 r 这样 rq\equiv p \pmod{998244353} 和 0\leq r < 998244353。你应该找到这个 r.

约束

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 全部 A_i 是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

3 2
3 7 5

示例输出 1

665496238

有以下三种可能的选择: K 整数,如下,以相等的概率选择。

\{3,7\}:这里我们有 X-Y=7-3=4.

\{3,5\}:这里我们有 X-Y=5-3=2.

\{7,5\}:这里我们有 X-Y=7-5=2.

预期值为 \dfrac{4+2+2}{3}=\dfrac{8}{3},模 998244353 is 665496238.


示例输入 2

3 1
3 7 5

示例输出 2

0

示例输入 3

10 5
384 887 778 916 794 336 387 493 650 422

示例输出 3

621922587