神奇的计数题。

首先考虑 f(p)f(p) 的本质是什么。

f(p)=∑1≤i<j≤n,pi>pjj−i=∑1≤i<j≤n,pi>pjj−∑1≤i<j≤n,pi>pji=∑i=1ni∑j=1i−1[pi<pj]−∑i=1ni∑j=i+1n[pi>pj]=∑i=1ni(∑j=1i−1[pi<pj]−∑j=i+1n[pi>pj])\begin{aligned} f(p) &= \sum_{1 \le i < j \le n,p_i > p_j} j - i\\ &= \sum_{1 \le i < j \le n,p_i > p_j} j - \sum_{1 \le i < j \le n,p_i > p_j} i\\ &= \sum_{i = 1}^n i\sum_{j = 1}^{i - 1}[p_i < p_j] - \sum_{i = 1}^n i\sum_{j = i + 1}^n [p_i > p_j]\\ &= \sum_{i = 1}^n i\left(\sum_{j = 1}^{i - 1}[p_i < p_j] - \sum_{j = i + 1}^n [p_i > p_j]\right)\\ \end{aligned}

这样，我们就成功的把 j−ij - i 拆成了 ii 和 jj 分别的贡献。然后，设 g(i)=∑j=1i−1[pi<pj]−∑j=i+1n[pi>pj]g(i) = \sum_{j = 1}^{i - 1}[p_i < p_j] - \sum_{j = i + 1}^n [p_i > p_j]，则 f(p)=∑i=1ni×g(i)f(p) = \sum_{i = 1}^n i \times g(i)。

g(i)=∑j=1i[pi<pj]−∑j=i+1n[pi≥pj]=i−∑j=1i[pi≥pj]−∑j=i+1n[pi≥pj]=i−∑j=1n[pi≥pj]=i−pi\begin{aligned} g(i) &= \sum_{j = 1}^i[p_i < p_j] - \sum_{j = i + 1}^n [p_i\ge p_j]\\ &= i - \sum_{j = 1}^i[p_i \ge p_j] - \sum_{j = i + 1}^n [p_i \ge p_j]\\ &= i - \sum_{j = 1}^n[p_i \ge p_j]\\ &= i - p_i\\ \end{aligned}

我们就得出了 f(p)=∑i=1ni(i−pi)f(p) = \sum_{i = 1}^n i(i - p_i) 的结论。

然后，我们就只需要求出初始在位置 ii 的元素操作 mm 次后到达的位置的期望 sis_i，则答案为 (n+12)m∑i=1ni2−si×pi\binom{n + 1}2^m\sum_{i = 1}^n i^2 - s_i \times p_i。

这个东西看着很棘手，怎么办呢？我们考虑继续挖掘性质。

我们考虑一个点 ii。通过一次操作把它挪到点 jj 的方案数显然是 min⁡(i,n−i+1,j,n−j+1)\min(i, n - i + 1, j, n - j + 1)，所以我们可以发现，把 ii 挪到 jj 的概率和挪到 n−j+1n - j + 1 的概率是一样的。

于是，无论一个点处在何位置，它受到操作影响之后，期望位置就会变为 n+12\frac{n + 1}2。

所以一个点 ii 如果没被任何操作包含（概率为 q=(1−2i(n−i+1)n(n+1))mq = (1 - \frac{2i(n - i + 1)}{n(n+1)})^m），它的期望位置就是 ii；如果它被任意一个操作包含（概率为 1−q1 - q），它的期望位置就是 n+12\frac{n + 1}2。把两个综合一下，得到 si=qi+(1−q)n+12s_i = qi + (1 - q)\frac{n + 1}2。

每个 sis_i 都可以 O(log⁡m)O(\log m) 算，总时间复杂度为 O(nlog⁡m)O(n \log m)。