【題解】AtCoder ABC 151E – Max-Min Sums

【題目敘述】https://atcoder.jp/contests/abc151/tasks/abc151_e

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
 
const int maxn = 400005;
ll pre[maxn];
ll inv[maxn];
ll prei[maxn];
ll mod = 1000000007;
int n, k;
 
void build(int n){
    pre[1] = pre[0] = 1;
    inv[1] = inv[0] = 1;
    prei[1] = prei[0] = 1;
    for(int i = 2 ; i <= n ; i++){
        pre[i] = pre[i-1] * i % mod;
        inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
        prei[i] = prei[i-1] * inv[i] % mod;
    }
}
 
ll C(int n, int k){
   return pre[n] * prei[k] % mod * prei[n-k] % mod;
}
 
int main() {
    build(maxn-2);
    cin >> n >> k;
    int a[maxn];
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    long long ans = 0;
    for (int i = 1; i <= n-k+1; i++){
        ans -= C(n-i, k-1) * a[i] % mod;
        ans += mod;
        ans %= mod;
    }
    for (int i = k; i <= n; i++){
        ans += C(i-1, k-1) * a[i] % mod;
        ans %= mod;
    }
    cout << ans << "\n";
}
分享本文 Share with friends