CF513G3 Inversions problem

给定一个长度为 $n$ 的排列 $p_{1},p_{2},...,p_{n}$。我们进行 $k$ 次如下操作：每次等概率随机选择两个下标 $l$ 和 $r$（$l \leq r$），然后将区间 $p_{l},p_{l+1},...,p_{r}$ 的元素顺序反转。你的任务是求经过 $k$ 次操作后，排列中逆序对数量的期望值。 本题包含三个子任务。不同子任务对输入有不同的限制。正确提交子任务可以获得相应分数。子任务描述如下： - 子任务 G1（$3$ 分）：$1 \leq n \leq 6$，$1 \leq k \leq 4$。 - 子任务 G2（$5$ 分）：$1 \leq n \leq 30$，$1 \leq k \leq 200$。 - 子任务 G3（$16$ 分）：$1 \leq n \leq 100$，$1 \leq k \leq 10^{9}$。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100$，$1 \leq k \leq 10^{9}$）。 第二行包含 $n$ 个整数 $p_{1},p_{2},...,p_{n}$，表示给定的排列。所有 $p_{i}$ 互不相同，且在 $1$ 到 $n$ 之间。

输出一个实数，表示期望逆序对数量，绝对误差或相对误差不超过 $1e-9$。

以第一个样例为例。我们会随机选择排列 $(1,2,3)$ 的一个区间（初始没有逆序对），并反转该区间。以概率 $\frac{1}{6}$，选择的区间只包含一个元素，排列不变。以概率 $\frac{1}{6}$，我们会反转前两个元素，得到排列 $(2,1,3)$，有一个逆序对。以同样的概率，可能选择后两个元素，得到排列 $(1,3,2)$，也有一个逆序对。最后，以概率 $\frac{1}{6}$，选择整个区间，得到排列 $(3,2,1)$，有三个逆序对。因此，期望逆序对数量为 $\frac{1}{6} \times 0 + \frac{1}{6} \times 1 + \frac{1}{6} \times 1 + \frac{1}{6} \times 3 = 0.833333...$。 由 ChatGPT 4.1 翻译