首先，期望数乘上 \(\dbinom n2^k\) 后得到的就是所有方案的逆序对数之和。
任取两个位置 \(A, B(A < B)\)，不难看出其他任意位置对 \(A, B\) 而言都是等价的，把这些位置统称为 \(C\) 位置。
然后 \((A, B)\) 最终的样子只有以下七种形式：\((A, B), (A, C), (B, A), (B, C), (C, A), (C, B), (C, C)\)，把这七种形式从 \(1\) 到 \(7\) 编号。
设 \(f_j(i)\) 表示交换 \(i\) 次后形如第 \(j\) 种形式的方案数：
\(k \le 10^9\)，考虑矩阵优化，写出转移矩阵：
\[\begin{bmatrix} f_1(i - 1) \\ f_2(i - 1) \\ f_3(i - 1) \\ f_4(i - 1) \\ f_5(i - 1) \\ f_6(i - 1) \\ f_7(i - 1) \end{bmatrix} \times \begin{bmatrix}
\binom n{n - 2} & 1 & 1 & 0 & 0 & 1 & 0 \\
n - 2 & \binom{n - 2}2 + (n - 3) & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & \binom{n - 2}2 & 1 & 1 & 0 & 0 \\
0 & 1 & n - 2 & \binom{n - 2}2 + (n - 3) & 0 & 1 & 1 \\
0 & 1 & n - 2 & 0 & \binom{n - 2}2 + (n - 3) & 1 & 1 \\
n - 2 & 0 & 0 & 1 & 1 & \binom{n - 2}2 + (n - 3) & 1 \\
0 & n - 3 & 0 & n - 3 & n - 3 & n - 3 & \binom{n - 2}2 + 2(n - 4) + 1
\end{bmatrix}
= \begin{bmatrix} f_1(i) \\ f_2(i) \\ f_3(i) \\ f_4(i) \\ f_5(i) \\ f_6(i) \\ f_7(i) \end{bmatrix}
\]
其中 \(f_1(0) = 1, f_2(0) = f_3(0) = \dots = f_7(0) = 0\)。
然后我们开始枚举数对 \((i, j)(i < j)\)，若 \(a_i < a_j\)：
- \((A, B)\)，必然没有贡献。
- \((A, C)\)，\(C\) 在 \(A\) 前就有贡献，贡献为 \(\dfrac{i - 1}{n - 2} \times f_2(k)\)。
- \((B, A)\)，必然有贡献，贡献为 \(f_3(k)\)。
- \((B, C)\)，\(C\) 在 \(B\) 前就有贡献，贡献为 \(\dfrac{j - 1}{n - 2} \times f_4(k)\)。
- \((C, A)\)，\(C\) 在 \(A\) 后且不是 \(B\) 就有贡献，贡献为 \(\dfrac{n - i - 1}{n - 2} \times f_5(k)\)。
- \((C, B)\)，\(C\) 在 \(B\) 后就有贡献，贡献为 \(\dfrac{n - j}{n - 2} \times f_6(k)\)。
- \((C, C)\)，相对位置交换成 \((j, i)\) 且不在 \(A\) 或 \(B\) 就有贡献，贡献为 \(\dfrac 12 f_7(k)\)。
\(a_i > a_j\) 同理。
套 BIT 优化以下，时间复杂度 \(\mathcal O(7^3\log k + n \log n)\)。
代码：