期待値の線形性より、 \(X\) の期待値 \(E[X]\) と \(Y\) の期待値 \(E[Y]\) をそれぞれ独立に求めてから引き算をすることで求める値を得ることができます。

\(A\) をソートすることで \(A\) が昇順に並んでいるとします。

相異なる \(K\) 個を無作為に選んだ時、最大値が \(A_i\) であるような確率を考えます。この確率を \(P_{max}(i)\) とすると、 \(\displaystyle E[X]=\sum_{i=1}^N A_iP_{max}(i) \) であることが分かります。

まず、相異なる \(K\) 個の要素を選ぶ方法は \(\displaystyle \binom NK\) 通りです。 そのうち最大値が \(A_i\) であるような選び方は最大値以外の要素の決め方を考えることで \(\displaystyle \binom{i-1}{K-1}\) 通りだと分かります。

以上より、 \(P_{max}(i)=\displaystyle \binom{i-1}{K-1}\binom{N}{K}^{-1}\) が分かるので、ここから \(\displaystyle E[X]=\binom{N}{K}^{-1}\sum_{i=1}^N\binom{i-1}{K-1}A_i\) が得られます。

同様にして、 \(\displaystyle E[Y]=\binom{N}{K}^{-1}\sum_{i=1}^N \binom{N-i}{K-1}A_i\) も分かります。

以上より、求める値は \(\displaystyle\binom{N}{K}^{-1}\sum_{i=1}^N \left(\binom{i-1}{K-1}- \binom{N-i}{K-1}\right)A_i\) なので、これを \(\text{mod}\ 998244353\) で計算することで正解となります。

計算量はソートがボトルネックとなり \(O(N\log N)\) です。

\(n<k\) に対し \(\displaystyle \binom nk=0\) であることに注意してください。

実装例(Java) (この実装では ACL for Java の ModInt を使用しています)