Max-Min Sums

题目描述

对于一个有限整数集合 $X$，令 $f(X)=\max X - \min X$。 给出 $N$ 个整数 $A_1,...,A_N$。 我们将从中选择 $K$ 个整数，令 $S$ 为所选整数构成的集合。如果即使数值相同也根据索引区分元素，那么共有 ${}_N C_K$ 种选择方式。求在所有这些选择方式中 $f(S)$ 的和。 由于答案可能非常大，请输出对 $(10^9+7)$ 取模的结果。

输入格式

输入采用标准输入，格式如下： $N$ $K$ $A_1$ $...$ $A_N$

输出格式

输出对 $(10^9+7)$ 取模的答案。

4 2
1 1 3 4

11

6 3
10 10 10 -10 -10 -10

360

3 1
1 1 1

0

10 6
1000000000 1000000000 1000000000 1000000000 1000000000 0 0 0 0 0

999998537

提示

$1 \leq N \leq 10^5$ $1 \leq K \leq N$ $|A_i| \leq 10^9$共有六种选择 $S$ 的方法：$\{1,1\},\{1,3\},\{1,4\},\{1,3\},\{1,4\}, \{3,4\}$（我们区分两个 $1$）。这些选择对应的 $f(S)$ 值分别为 $0,2,3,2,3,1$，总和为 $11$。
共有 $20$ 种选择 $S$ 的方法。在其中 $18$ 种中，$f(S)=20$，在 $2$ 种中，$f(S)=0$。
输出取模 $(10^9+7)$ 后的和。

标签: AtCoder|abc151E

来源

AtCoder|abc151E