AGC030D Inversion Sum

题意：给你一个长度为 的数列 ，然后给出 个交换操作。

设交换操作序列 按顺序使用后， 中逆序对的个数为 。

枚举 个操作的 个子集 ，求 的总和。

答案对 取模，，时限 。

---

较小，允许我们考虑每个（可能产生逆序对的）二元组。

维护 表示考虑完前 个操作后， 的情况数。

若不执行第 步交换，则有

若执行第 步交换 ：

其中，前五条所影响的状态量是 的。最后一条的效果是让某个位置乘以 ，可以利用时间戳懒处理，或转为维护期望。

最后对于所有 的 求和即可得到答案。

复杂度 。