分数: 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