题解

思路

利用期望的线性性，分别研究每一对元素在操作后是否形成逆序。区间反转只在同时包含这两个元素时改变它们的相对顺序，因此可在“两元素位置”状态上做概率 DP。

做法

子任务 1

维护“排列到概率”的映射。枚举每一步的所有区间并真正反转，最后按概率加权求逆序对数。状态数至多 $n!$。

子任务 2

设 $f_t(i,j)$ 表示两个元素当前位于 $i<j$，且当前相对顺序为正时，再做 $t$ 次操作后相对顺序的期望符号，其中同序为 $1$、逆序为 $-1$，有 $f_0(i,j)=1$。

枚举一次操作的区间。区间可能不含两个位置、只含左端元素、只含右端元素或同时包含二者。前三类保持符号，最后一类翻转符号。直接枚举转移后的另一位置即可在 $O(n^3)$ 时间完成一层 DP，足以通过 $n\le30,k\le200$。

满分算法

记 $A=i+1$、$B=j-i$、$C=n-j$（下标从 $0$ 开始）。

• 只包含位置 $i$ 的区间把它送到 $x$ 的方案数，是两个全一序列长度 $A,B$ 的卷积系数；
• 只包含位置 $j$ 时对应长度 $B,C$ 的卷积；
• 同时包含二者时，新位置差仍为 $j-i$，对应长度 $A,C$ 的卷积，并且符号取反。

两个全一序列的卷积系数呈“递增、平台、递减”的三段一次函数。对 DP 的每一行、每一列和每条等差对角线同时维护普通前缀和与下标加权前缀和，就能在 $O(1)$ 时间求出每一段加权和，从而把一层转移降为 $O(n^2)$。

该随机过程的反对称部分快速收敛到零。对 $n\le100$ 的全部状态，做满 $1000$ 步后剩余项已低于题目 $10^{-9}$ 相对误差所需的保守界，因此令实际迭代次数为 $\min(k,1000)$。

得到 $f_k(i,j)$ 后，若初始时 $p_i>p_j$，该对形成逆序的概率为 $(1+f_k(i,j))/2$；否则为 $(1-f_k(i,j))/2$。累加所有位置对即为答案。

复杂度

子任务 1 为 $O(k\,n!\,n^2)$；子任务 2 为 $O(kn^3)$；满分算法时间复杂度为 $O(n^2\min(k,1000))$，空间复杂度为 $O(n^2)$。