更好的阅读体验：TonyYin’s Blog ↗
题目地址：AT4846 [ABC151E] Max-Min Sums - 洛谷 _ 计算机科学教育新生态 ↗
#
给定 个数，构成集合 。从 中任取 个数，构成 的子集 .
记 为 中的最大值， 为 中的最小值，.
题目要求：所有满足 的 之和。（对 取模）
#
观察数据范围，期望时间复杂度为： 或者 的做法。
暴力的方法就是 枚举元素个数为 的子集，然后找最大值和最小值，复杂度爆炸，期望得分 分.
考虑集合的无序性。
将集合内的元素升序排序，之后发现可以计算每个数可能在多少个子集中成为最大值/最小值。
考虑如何统计作为子集中最大值的次数。
具体地，对于前 个数，不可能成为任何一个子集的最大值；对于其余的数，第 个数成为最大值的方法数是 种，也就是在前 个数中取 个，与第 个数一起构成子集，这样的子集能使 为最大值。
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部分的代码有取模。在这个数据范围下，使用逆元求组合数就可以了，如果不会用逆元求组合数，可以看一下我写的这篇博客 ↗，往下翻，可以找到关于组合数取模的部分。
#
给出完整的代码。
#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;
}