CF513G2 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{3}{6}$，此时排列不变。 选择前两个元素的区间的概率为 $\frac{1}{6}$，得到排列 $(2,1,3)$，有一个逆序对。 选择后两个元素的区间的概率也为 $\frac{1}{6}$，得到排列 $(1,3,2)$，有一个逆序对。 选择整个排列的区间的概率为 $\frac{1}{6}$，得到排列 $(3,2,1)$，有三个逆序对。 因此，期望的逆序对数为 $\frac{1}{2} \times 0 + \frac{1}{6} \times 1 + \frac{1}{6} \times 1 + \frac{1}{6} \times 3 = \frac{5}{6}$。 由 ChatGPT 4.1 翻译