周赛84——G：组合数+贡献法的经典考点

蒟蒻的第二篇题解，以后尝试在牛客发表我这个蒟蒻的理解（大佬勿喷）

改试卷改到8点半，没来得及打了/(ㄒoㄒ)/~~，

组合计数最常考的就是搭配贡献法，如果报名了寒假训练营的可以去把寒假5的H题（稍微比这题有点难度，当时wa了6次）再写一遍。

这题因为要全排序，然后又让我们求每两个数的差，我们可以先这样考虑：

1：对于单独的1个数：ai， 怎么算贡献比较好算？（因为求的是绝对值，直接算的话函数极值点太多了）

2：算出一个贡献后，我们有多少种情况？（注：题目规定贡献是：ai 和 ai+1）

对于问题1：我们求ai的贡献，无非就是和所有数字去组合一下（也就是 ai 和 a1, a2, a3 ...... an （除了自己））

这个怎么算？有人会说直接用一个计数器，然后用 sum - ai 就好了

但是我们求的是绝对值，这么算显然是比正确小，因为对于 ak （ak < ai）来说，这么算就是负数，而取绝对值就是正数。

那么怎么算好呢？

我们稍加思考就会发现，我们只要把数组排序后，这个问题就解决啦！

因为这样一来就是个升序数组，这样就可以用前缀和维护了；

对于比 ai 小的数， 我们的贡献显然是 (i - 1)ai - s[i - 1]；

对于比 ai 大的数， 我们的贡献显然是 s[n] - s[i] - (n - i)ai；

这样第一个问题就解决了

对于问题2：对于我们这个贡献，我们可以把这两坨玩意放到任何一个地方，也就是捆绑；

（这里不能交换，因为交换之后我们的贡献就变化了）

然后对于剩余的 n - 2 个数字可以随便排列

那么我们的情况数量就是 （n - 2）！ * (n - 1) = （n - 1）!

最后整个序列的全排列的总数是 n !

答案就是把贡献 ans * （n - 1）！/ n！= ans / n

（别忘记给前缀和取模，这里wa了2次）

#include<bits/stdc++.h>

#define lc p << 1
#define rc p << 1 | 1
#define lowbit(x) x & -x
#define inv(x) qmi(x, P - 2)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef unsigned __int128 ulll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<lll,lll> pLL;
const ll N = 2e5 + 10, inf = 0x3f3f3f3f, INF = 0x3f3f3f3f3f3f, P = 1e9 + 7;
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[] = {0, 1, 0, -1, -1, 1, -1, 1};

int T = 1;
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return res;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n + 10), s(n + 10);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n);

    for(int i = 1; i <= n; i ++) s[i] = (s[i - 1] + a[i]) % P;
    ll ans = 0;
    for(ll i = 1; i <= n; i ++){
        ll pre = (i - 1) * a[i] % P - s[i - 1];
        if(pre < 0) pre = (pre + P) % P;
        ll last = (s[n] - s[i] - ((n - i) * a[i] % P));
        if(last < 0) last = (last + P) % P;
        ans = (ans + pre + last) % P; 
    }   
    cout << ans * inv(n) % P << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    //cin >> T;
    while(T --){
        solve();
    }
    return 0;
}