随机逆序对 题解

题意

给定 $1\sim n$ 的排列 $a_{1...n}$ 。在上面进行依次如下操作：

1. 首先在$[1,n]$​中选取一个子序列(可以为空);

2. 然后将这个子序列内的数重新排列。

两个操作不同，当且仅当选取的子序列不同或者重新排列的方式不同。对于所有不同的操作，求他们产生的排列的逆序对个数和，答案对$10^9+7$​取模。

题解

首先，看到这个题目我们发现整体方案数并不好枚举，所以说考虑拆分贡献。

我们先思考朴素的 $O(n^3)$ 的做法，我们枚举 $3$ 个元素分别为目前逆序对会产生贡献的两个数字，以及目前选了多少个数字。我们设 $pos_i$ 为 $i$ 这个值在序列中的位置那么我们就可以得到以下式子。

1. $pos_i$$>pos_j$​

方案数分别为我们只影响到 $2$ 个数字，的贡献要算 $4$ 倍是因为这两个点不一定全部都要在交换序列中，因为他们本身顺序都是一样的。然后就是我们影响到 $3$ 个位置的，有几种情况。分别是 $i$ 动 $j$ 不动，$i$ 不动 $j$ 动，$i$ 到 $j$ 的位置 $j$ 动， $j$ 到 $i$ 的位置 $i$ 动，情况数也是好统计的，和之前的差不多可以自行证明。最后就是 $4$ 个位置的情况，也很简单，直接枚举除了 $i,j$ 两个点的位置即可。 唯一需要注意的是有些时候有些位置并不需要在选择的需要排列的序列中导致的贡献增加，记得细心推式子。
$$
4\sum\limits_{i=1}^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-2}(k-2)!
+2\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=3}^{n}C{k-3}(k-3)!(n-pos_j-1)
+2\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-3}(k-3)!(pos_i-2)
+\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-3}(k-3)!(pos_j-1)
+\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-3}(k-3)!(n-pos_i)
+\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C_{k-4}(k-4)!\frac{(n-3)\times(n-2)}{2}
$$

2. $pos_i<pos_j$​

情况和上述差别不大可以自行推导。
$$
\sum\limits_{i=1}^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-2}(k-2)!
+2\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=3}^{n}C{k-3}(k-3)!(n-pos_j)
+2\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-3}(k-3)!(pos_i-1)
+\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-3}(k-3)!(pos_j-2)
+\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C{k-3}(k-3)!(n-pos_i-1)
+\sum\limits^{{n}\sum\limits_{j=i+1}}\sum\limits_{k=2}^{n}C_{k-4}(k-4)!\frac{(n-3)\times(n-2)}{2}
$$
我们可以发现其实后面的 $k$ 其实可以不用枚举，每一次的结果都是一样的，系数也是相同所以可以直接预处理就可以把时间复杂度降到 $O(n^2)$。

最后我们发现其实我们只用枚举 $i$ ，但其实 $j$ 的加起来的和和数量是可以维护的，所以说只需要写一个树状数组维护即可。时间复杂度降到了 $O(n\log n)$。可以通过此题。