$\rm{Description}$

给定 $n$ 个数，构成集合 $A$。从 $A$ 中任取 $k$ 个数，构成 $A$ 的子集 $S$.

记 $\rm{Max}$ 为 $S$ 中的最大值，$\rm{Min}$ 为 $S$ 中的最小值，$f(S)=\rm{Max-Min}$.

题目要求：所有满足 $|S|=k$ 的 $f(S)$ 之和。（对 $1e9+7$ 取模）

$\rm{Solution}$

观察数据范围，期望时间复杂度为： $\mathcal{O}(n\log n)$ 或者 $\mathcal{O}(n\log |x|)$ 的做法。

暴力的方法就是 $C_n^k$ 枚举元素个数为 $k$ 的子集，然后找最大值和最小值，复杂度爆炸，期望得分 $0$ 分.

考虑集合的无序性。

将集合内的元素升序排序，之后发现可以计算每个数可能在多少个子集中成为最大值/最小值。

考虑如何统计作为子集中最大值的次数。

具体地，对于前 $k – 1$ 个数，不可能成为任何一个子集的最大值；对于其余的数，第 $i$ 个数成为最大值的方法数是 $C_{i-1}^{k-1}$ 种，也就是在前 $i-1$ 个数中取 $k-1$ 个，与第 $i$ 个数一起构成子集，这样的子集能使 $i$ 为最大值。

for(int i = k; i <= n; i++) { //算一遍最大值
	ans += a[i] * C(i - 1, k - 1);
}
//为了美观，这里的代码没有取模。下面Code部分的代码有取模。

对于统计作为子集中最小值的次数，与最大值同理。

for(int i = 1; i <= n - k + 1; i++) { //算一遍最小值
	ans -= a[i] * C(n - i, k - 1);
}
//为了美观，这里的代码没有取模。下面Code部分的代码有取模。

在这个数据范围下，使用逆元求组合数就可以了，如果不会用逆元求组合数，可以看一下我写的这篇博客，往下翻，可以找到关于组合数取模的部分。

$\rm{Code}$

给出完整的代码。

#include <bits/stdc++.h>
#define int long long
#define MAXN 100008
using namespace std;
int mod = 1e9 + 7;
int n, k, a[MAXN], fac[MAXN], ans = 0;
int power(int x, int k, int p) {
	int ret = 1;
	while(k) {
		if(k & 1) ret = ret * x % p;
		k >>= 1;
		x = x * x % p;
	}
	return ret % p;
}
int inv(int x, int p) {//求x关于模p的逆元
	return power(x, p - 2, p) % mod;
}
int C(int a, int b) {//直接用逆元求解组合数C(a, b)
	return fac[a] * inv(fac[b], mod) % mod * inv(fac[a - b], mod) % mod;
}
signed main() {
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	fac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
	sort(a + 1, a + n + 1); //升序排序
	//对于每个数，计算在多少种个子集中，这个数能作为最大值/最小值
	//作为最大值的可能情况是C(i - 1, k - 1)，最小值类似
	for(int i = k; i <= n; i++) { //算一遍最大值
		ans = (ans + a[i] * C(i - 1, k - 1) % mod) % mod;
	}
	for(int i = 1; i <= n - k + 1; i++) { //算一遍最小值
		ans = (ans - a[i] * C(n - i, k - 1) % mod) % mod;
	}
	cout << (ans % mod + mod) % mod << endl;
	return 0;
}