Luogu4223 期望逆序对

题意 ：给你一个长为 的排列 ，有 次操作，每次随机选择两个不同的数交换，共 种情况中问逆序对数的和。

答案对 取模，，，时限 。

---

考虑某对数 ，设两者最终的位置为 ，分 类情况讨论 ：

其中 指某个不等于 的位置。由于随机交换，每个这样的 出现的概率都相同。

若我们已经知道了七种情况各自的方案数，考虑如何求这对 之间的贡献总和。

对每种情况求出能贡献一个逆序对的概率：

• ：

• ：

• ：

• ：

• ：

• ：

• ：

这些都可以转化为二维偏序后使用树状数组求解。

交换的方案数可以用 配合矩阵快速幂求解。

设 表示交换 次后为第 种情况的方案数，转移矩阵为 ：

检查该矩阵时，可以查看每一列的和是否恰为 。

时需要特判。

复杂度 。