P4223 期望逆序对
注意到期望的线性性，所以这类题目的做法一般都是单独考虑一对数之间的贡献是多少
我们用 \(f[t][i][j][0/1]\) 表示第 \(t\) 轮，两个数分别在 \(i,j\)，对答案是否有贡献
转移可以利用前缀和转移，这样的复杂度是 \(\mathcal O(n^2k)\)
考虑两个数 \(a_i,a_j\)，设他们两个数开始的位置是 \(A,B\)，其他的位置是 \(C\)，那么最终的位置一共只有 7 种可能性
\((A,B),(A,C),(B,A),(B,C),(C,A),(C,B),(C,C)\)
这几种位置关系之间是可以递推的，递推的过程中可以使用矩阵乘法来加速 dp
考虑最后如何计算贡献
不妨设 \(a_i<a_j\)，那么有
\((A,B)\) 的贡献为 \(0\)
\((B,A)\) 的贡献为 \(1\)
\((A,C)\) 的贡献为 \(\dfrac{A-1}{n-2}\)
\((B,C)\) 的贡献为 \(\dfrac{B-2}{n-2}\)
以此类推
我们枚举 \(A,B\)，用树状数组维护计算贡献即可