牛客小白月赛61 E.排队（组合数学）

对于n个数，求其所有可能排列中的逆序数之和

解题思路：

求每种排列逆序数之和，因为数字的顺序在变化，这对我们去计算总和很不利，所以我们转换思路我们可以先考虑数对（a,b）逆序数对整体的贡献（先固定住数）
（a,b）可以形成的排列有C\(\tbinom{1}{n}\)*C\(\tbinom{1}{n-1}\)*A\(\tbinom{1}{n}\)种（组合数，n个位置里选一个放a,n-1个位置里选一个放b,剩下(n-2)个数随机排列）但是因为我们只要逆序数，因为<a,b>和<b,a>各有二分之一的可能,我们只要a>b的,所以逆序数排列有:\({{n*(n-1)*(n-2)!} \over {2}}\)
然后总和就为:\(\displaystyle \sum _{i=0}^{i = cnt}{{n*(n-1)*(n-2)!} \over {2}}\),也就是每一对（a,b）都会有相同的贡献,剩下的只需要计算有多少对（a,b）即可

代码实现：

# include<bits/stdc++.h>
using namespace std;
# define int long long
const int  N = 1e5+10,mod = 1e9+7;
int a[N];
int b[N];
signed main(){
    int n;
    cin>>n;
    b[1] = 1;
    for(int i = 2;i <= N;++i) b[i] = b[i-1]*i%mod;\\预处理阶乘
    for(int i = 1;i <= n;++i) cin>>a[i];
    if(n == 1) {
        cout<<0<<endl;
        return 0;
    }
    int p = (n*(n-1)/2)%mod*b[n-2]%mod;\\求贡献
    int cnt = 0;
    sort(a+1,a+1+n);
    for(int i = 1;i <= n;++i){
        int pos = lower_bound(a+1,a+1+n,a[i])-(a+1);\\计算数对
        cnt += pos;
    }
    p = p*cnt%mod;\\总贡献
    cout<<(p+mod)%mod<<endl;   
    return 0;
}