题意

给你一个长度为n的序列，你需要对他进行全排列，求每种序列的逆序对有多少，然后求每种序列逆序对之和。

思路

如果这个长度为n的序列如果没有重复的数字，这个逆序对之和公式为 n ∗ ( n − 1 ) ∗ f a [ n ] 4 \frac{n*(n-1)*fa[n]}{4} 4n∗(n−1)∗fa[n]​。
推理公式
但是这个序列还有重复的数字，例如1 2 3 3这个序列，我们应该按照1 2 3 4这样计算，但是这儿有两个3，所以我们应该把3 4这一组数字的所有贡献减去。而3 4在整个长度为n的序列中一共会出现 4 ! 2 ! \frac{4!}{2!} 2!4!​这么多次，因为3 4也会有排列。然后3 4 每次会贡献 2 ∗ ( 2 − 1 ) ∗ f a [ 2 ] 4 \frac{2*(2-1)*fa[2]}{4} 42∗(2−1)∗fa[2]​，所以说我们应该在原来没有重复的基础上，减去这些重复元素的贡献也就是3 4的贡献。所以最终答案为： n ∗ ( n − 1 ) ∗ f a [ n ] 4 − 4 ! 2 ! ∗ 2 ∗ ( 2 − 1 ) ∗ f a [ 2 ] 4 \frac{n*(n-1)*fa[n]}{4} -\frac{4!}{2!}*\frac{2*(2-1)*fa[2]}{4} 4n∗(n−1)∗fa[n]​−2!4!​∗42∗(2−1)∗fa[2]​

因此我们只需要判断那些数字重复出现过多少次，在原来的基础上每次相减就是了。

代码

#include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define int long long 
#define endl "\n"
#define pb push_back 
#define pop_back pop using namespace std;const int N = 1e5 + 10, INF = 1e18 + 10, mod = 1e9 + 7;int arr[N], fa[N], ifa[N];
int n, m, k;int ksm(int a, int b)
{int ans = 1;while (b){if (b & 1) ans = a * ans % mod;a = a * a % mod;b >>= 1;}return ans;
}void init()
{fa[0] = 1;ifa[0] = 1;for (int i = 1; i < N; i++){fa[i] = (i * fa[i - 1]) % mod;ifa[i] = ksm(i, mod - 2) * ifa[i - 1] % mod;}
}signed main()
{IOS;init();int n;cin >> n;vector<int> a(n + 1);map<int, int>mp;for (int i = 1; i <= n; i++){cin >> a[i];mp[a[i]]++;}int ans = ((n * (n - 1)) % mod * fa[n] % mod * ksm(4, mod - 2) % mod) % mod;//不重复元素的贡献for (auto [k, v] : mp){if (v > 1)//减去重复的元素的贡献，可以化简公式把fa[v]给约掉{ans = (ans - (fa[n] * v % mod * (v - 1) % mod * ksm(4, mod - 2)) % mod + mod) % mod;}}cout << ans << endl;return 0;
}