题意：有一个长度为 \(N(\leq 3000)\) 的序列。有 \(Q(\leq 3000)\) 个操作 \((x_i,y_i)\)。每个操作可以选择是否执行；若执行，则交换 \(A_{x_i}\) 和 \(A_{y_i}\)。一共有 \(2^Q\) 种选择方法。问所有选择方法最终序列里的逆序对数量之和是多少。模一个大质数。
题解：这题容易陷入思维僵局。比如先枚举某一个位置 \(k\)，然后设 \(f_{i,j}\) 表示到第 \(i\) 个操作，我们关注的那个数字现在在 \(j\) 的期望/总方案数。最后枚举两个数合成，总复杂度是 \(O(N^2Q)\)。其实每次操作很“稀疏”（只和两个位置有关），但是这种方法却必须维护好所有位置。
标准做法是，设 \(f_{t,i,j}\) 表示进行了 \(t\) 轮后，当前第 \(i\) 个位置的数字大于第 \(j\) 个的概率。每次转移时发现，只有其中一个数字是 \(x_i\) 或 \(y_i\) 的位置 \((i,j)\) 才会被修改，别的直接继承（这也是为什么要用概率来表示，因为概率是直接继承，方案数要集体乘 \(2\)）。每次修改的状态数只有 \(O(N)\) 个，所以总复杂度降为 \(O(NQ)\)。
原文：https://www.cnblogs.com/jiangshibiao/p/10360567.html