思路
考虑将 \(\max\) 和 \(\min\) 的贡献分开计算。
显然我们对这个序列进行一次排序不会影响最终的答案,因此我们可以先排序一下。
然后有一个很经典的 trick,就是你枚举每一个数 \(x\),将 \(x\) 令为最大值(最小值)。因为我们先前排序过一次,因此我们可以轻易的计算出比 \(x\) 小(大)的数的数量,然后我们需要在这些数里面选出剩下的 \(k - 1\) 个数,直接组合数算一下,得出方案数 \(num\)。那么 \(x\) 的贡献就是 \(num \times x\)。
Code
#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) % mod + (b) % mod) % mod)
#define Sub(a,b) (((a) % mod - (b) % mod + mod) % mod)
#define Mul(a,b) (((a) % mod) * ((b) % mod) % mod)
using namespace std;
const int N = 1e5 + 10,mod = 1e9 + 7;
int n,k,a,b;
int arr[N],fac[N],inv[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int qmi(int a,int b){
int res = 1;
while (b){
if (b & 1) res = Mul(res,a);
a = Mul(a,a);
b >>= 1;
}
return res;
}
inline void init(){
fac[0] = 1;
for (re int i = 1;i <= n;i++) fac[i] = Mul(fac[i - 1],i);
inv[n] = qmi(fac[n],mod - 2);
for (re int i = n - 1;~i;i--) inv[i] = Mul(inv[i + 1],i + 1);
}
inline int C(int n,int m){
if (n < m) return 0;
return Mul(Mul(fac[n],inv[m]),inv[n - m]);
}
signed main(){
n = read();
k = read();
init();
for (re int i = 1;i <= n;i++) arr[i] = read();
sort(arr + 1,arr + n + 1);
for (re int i = 1;i <= n;i++){
a = Add(a,Mul(C(n - i,k - 1),arr[i]));
b = Add(b,Mul(C(i - 1,k - 1),arr[i]));
}
printf("%lld",Sub(b,a));
return 0;
}
标签:排序,abc151,Min,int,题解,fac,mod,define
From: https://www.cnblogs.com/WaterSun/p/18261941