题意：给定一个 \(1\) 到 \(n\) 的排列，等概率选一段区间 \([l, r]\) 随机排序，求期望逆序对数。
\[E = \dfrac{\sum(cnt_{[1, n]} - cnt_{[l, r]} + E_{len})}{\dfrac{n \times (n + 1)}{2}} \]\(cnt_{[l, r]}\) 表示原序列 \([l, r]\) 内部逆序对数。
\(E_{len}\) 表示长度为 \(r - l + 1\) 的排列随机排序后的期望逆序对。
\(E_i\) 怎么求？（直接oeis，啪的一下很快啊
因此
\[\begin{aligned} E =& cnt_{[1, n]} - \dfrac{\sum cnt_{[l, r]}}{\dfrac{n \times (n + 1)}{2}} + \dfrac{\sum_{i = 1}^n (n - i + 1) \times E_i}{\dfrac{n \times (n + 1)}{2}} \\ =& cnt_{[1, n]} - \dfrac{2\sum cnt_{[l, r]}}{n \times (n + 1)} + \dfrac{\sum_{i = 1}^n (n - i + 1) \times i \times (i - 1)}{2 \times n \times (n + 1)} \\ =& A + \dfrac{-2B + \dfrac{C}{2}}{n \times (n + 1)} \end{aligned} \]\(A\)，\(C\) 都很好做。
对于 \(B\)，下标为 \(j, i\) 的逆序对对 \(B\) 的贡献为 \(j \times (n - i + 1)\)，树状数组维护 \(\sum j\) 即可。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
struct Fenwick_Tree {
ll t[::N], n;
void init(int x) {
for(int i = 1; i <= (n = x); ++ i) {
t[i] = 0;
}
}
void add(int p, ll v = 1) {
while(p) {
t[p] += v;
p -= p & -p;
}
}
ll suf(int p) {
ll ret = 0;
while(p <= n) {
ret += t[p];
p += p & -p;
}
return ret;
}
} bit;
ll n, a[N], A, B, C;
/*
长度为n的排列的期望逆序对数为 n * (n - 1) / 4
https://oeis.org/A001809
*/
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n, bit.init(n);
for(int i = 1; i <= n; ++ i) {
cin >> a[i];
A += bit.suf(a[i]);
bit.add(a[i]);
}
bit.init(n);
for(int i = 1; i <= n; ++ i) {
B += ll(n - i + 1) * bit.suf(a[i]);
bit.add(a[i], i);
}
B *= 2;
for(int i = 1; i <= n; ++ i) C += ll(n - i + 1) * i * (i - 1);
C /= 2;
double E = A + (double)(-B + C) / (n * (n + 1));
cout << fixed << setprecision(12) << E;
return 0;
}