/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 6 点
問題文
N 個の整数 A_1,A_2,\ldots,A_N から相異なる K 個を選びます。ここで、どの K 個の組も等確率で選ばれます。
選んだ整数の最大値を X とし、最小値を Y とするとき、X-Y の期待値を \bmod\,998244353 で求めてください。
注意
この問題の制約のもとで、求める期待値は互いに素な 2 整数 p,q を用いて p/q で表せることが証明でき、rq\equiv p \pmod{998244353} かつ 0\leq r < 998244353 を満たす整数 r が一意に定まります。この 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 つで、全て等確率で選ばれます。
\{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} で、これを \bmod\,998244353 で表すと 665496238 です。
入力例 2
3 1 3 7 5
出力例 2
0
入力例 3
10 5 384 887 778 916 794 336 387 493 650 422
出力例 3
621922587
Score : 6 points
Problem Statement
From N integers A_1,A_2,\ldots,A_N, we will choose K distinct integers. Here, any combination of K of the integers is chosen with equal probability.
Let X and Y be the maximum and minimum values among the chosen integers, respectively. Find the expected value of X-Y, modulo 998244353.
Notes
Under the Constraints of this problem, it can be proved that the sought expected value can be represented as p/q using two coprime integers p,q, and there uniquely exists an integer r such that rq\equiv p \pmod{998244353} and 0\leq r < 998244353. You should find this r.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All A_i are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
3 2 3 7 5
Sample Output 1
665496238
There are three possible choices of K integers, as follows, chosen with equal probability.
\{3,7\}: Here we have X-Y=7-3=4.
\{3,5\}: Here we have X-Y=5-3=2.
\{7,5\}: Here we have X-Y=7-5=2.
The expected value is \dfrac{4+2+2}{3}=\dfrac{8}{3}, which modulo 998244353 is 665496238.
Sample Input 2
3 1 3 7 5
Sample Output 2
0
Sample Input 3
10 5 384 887 778 916 794 336 387 493 650 422
Sample Output 3
621922587