【[ABC151E] Max-Min Sums】题解

· · 题解

思路

我们不可能暴力枚举所有子集，所以考虑每个元素对答案的贡献。

注意到，在一个子集中，只有头尾两个元素对答案有贡献。当一个元素为子集中最大值时，对答案有一个正的贡献；当为最小值时，有一个负的贡献。
因此，只需要对于每个元素，求出其作为最大和最小值的次数就可以了。

我们先考虑最大值的情况，最小值同理。

显然，对于一个元素，其为子集中最大值，当且仅当其余元素都不大于该元素。
考虑排序，将大小关系转化为先后顺序。则对于一个下标 i，其作为最大值的子集为前 i-1 个元素中选出 k-1 个再加上它本身，即该元素的正贡献为 {i-1\choose k-1}A_i。

同理，负贡献为 {n-i\choose k-1}A_i，总贡献为 [{i-1\choose k-1}-{n-i\choose k-1}]A_i。

而计算组合数，对于能看到这里的选手来说，一定是 trivial 的。

显然有：

{n\choose m}\equiv n!(m!)^{-1}[(n-m)!]^{-1}\mod 10^9+7

预处理乘法逆元即可。

AC Code

#include <bits/stdc++.h>
#define UP(i, l, r) for(int i = (l); i <= (r); ++ i)
#define DN(i, l, r) for(int i = (r); i >= (l); -- i)
#define LUP(i, l, r) for(ll i = (l); i <= (r); ++ i)
#define LDN(i, l, r) for(ll i = (r); i >= (l); -- i)
#define FE(i, s) for(auto i : s)
#define PB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int INF = 0x3f3f3f3f, INFB = 0x3f, N = 1e5, MOD = 1e9 + 7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, k, a[N + 5];
ll fac[N + 5], ifc[N + 5], ans;

ll qpow(ll a, ll b){
    ll res = 1ll;
    for(; b; b >>= 1){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

ll md(ll x){ return (x % MOD + MOD) % MOD; }

ll c(ll n, ll m){ return n >= m ? (fac[n] * ifc[m] % MOD) * ifc[n - m] % MOD : 0; }

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    fac[0] = 1;
    UP(i, 1, n){
        cin >> a[i];
        fac[i] = fac[i - 1] * i % MOD;
    }
    ifc[n] = qpow(fac[n], MOD - 2);
    DN(i, 0, n - 1) ifc[i] = ifc[i + 1] * (i + 1) % MOD;
    sort(a + 1, a + n + 1);
    UP(i, 1, n) ans = md(ans + md(md(c(i - 1, k - 1) - c(n - i, k - 1))) * a[i]);
    cout << ans;
}