Max-Min Sums（组合计数，算贡献）

题意

对于一个有限集合\(X\)，令\(f(X) = \max X - \min X\)

给定\(N\)个整数\(A_1, A_2, \dots, A_N\)

我们要从中选择\(K\)个元素构成一个新的集合\(S\)。如果我们根据下标区分元素（即使两个数数值相同，如果下标不同，也认为它俩是不同的），总共有\(C_{N}^K\)中选择方式。

求出所有选择方式的\(f(S)\)之和。

题目链接：https://atcoder.jp/contests/abc151/tasks/abc151_e

数据范围

\(1 \leq N \leq 10^5\)

思路

因为\(f(S)\)只与集合的最大值和最小值有关，因此我们考虑某个元素作为集合最大值、集合最小值的情况。

我们观察到\(\sum f(S) = \sum \max_S X - \min_S X = \sum \max X - \sum \min X\)。

因此我们只需要分别计算每个元素的贡献，即有多少次作为最大值，有多少次作为最小值

按照从小到大排完序之后，\(res = \sum_{i=1}^n (C_{i-1}^{k-1}a_i - C_{n-i}^{k-1} a_i)\)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100010, mod = 1e9 + 7;

int n, k;
ll a[N];
ll fac[N], infac[N];

ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

ll inv(ll a)
{
    return qmi(a, mod - 2);
}

ll C(ll x, ll y)
{
    return fac[x] * infac[y] % mod * infac[x - y] % mod;
}

void init()
{
    fac[0] = infac[0] = 1;
    for(int i = 1; i < N; i ++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 1; i < N; i ++) infac[i] = infac[i - 1] * inv(i) % mod;
}

int main()
{
    scanf("%d%d", &n, &k);
    init();
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    ll ans = 0;
    for(int i = k; i <= n; i ++) ans = (ans + C(i - 1, k - 1) * a[i] % mod) % mod;
    for(int i = 1; i <= n - k + 1; i ++) ans = (ans - C(n - i, k - 1) * a[i] % mod + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}