CF749E Inversions After Shuffle

给你一个由 $1$ 到 $n$ 的整数排列。现在你需要对该排列执行如下操作恰好一次： 1. 随机选取一个区间（连续子序列）$[l, r]$，所有 $\frac{n(n+1)}{2}$ 个区间都是等概率的。 2. 设 $k = r - l + 1$，即所选区间的长度。然后对区间内的这 $k$ 个元素，随机取一个排列 $p_1,p_2,\dots,p_k$，所有 $k!$ 种排列均等概率。 3. 用这个排列重排区间元素，即排列 $a_1,a_2,\dots,a_{l-1},a_l,a_{l+1},\dots,a_{r-1},a_r,a_{r+1},\dots,a_n$ 变为 $a_1,a_2,\dots,a_{l-1},a_{l-1+p_1},a_{l-1+p_2},\dots,a_{l-1+p_k},a_{r+1},\dots,a_n$。 「逆序对」指的是下标满足 $i < j$ 且 $a_i > a_j$ 的元素对。请你求恰好执行上述操作一次后，排列的逆序对期望数量。

第一行包含一个整数 $n$（$1 \le n \le 100000$），表示排列的长度。 第二行包含 $n$ 个互不相同的整数，表示排列的每一个元素，且它们为 $1$ 到 $n$ 的一个排列。

输出一个实数，表示操作后逆序对数的期望。答案的绝对误差或相对误差不能超过 $10^{-9}$。 具体来说，若你的输出为 $a$，标准答案为 $b$，则检查器会判定 $\frac{|a-b|}{\max(1,b)} \leq 10^{-9}$ 时你的答案正确。

由 ChatGPT 5 翻译