题解：AT_arc218_e [ARC218E] Reverse and Reverse

dyc2022 · 2026-05-06 13:09:47 · 题解

更好的阅读体验

终于读懂了官解。

我们考虑将 (p_1, p_2, \cdots, p_n) 变成 (p_i, p_{i-1}, \cdots, p_1, p_n, p_{n-1}, \cdots p_{i+1}) 这个操作是在干什么。容易发现，这个操作可以等价为，先 reverse 这个序列，再循环右移 i 位；而这个操作同样可以看作，先循环右移 n-i 位，然后 reverse 这个序列。

下文中 \text{rev. = reverse, rot. = rotate}。那么我们先用第一种表示方法，把操作序列写下来，比如 \text{rev.} \to \text{rot.}\to \text{rev.} \to \text{rot.} \to \cdots。由上一段的内容容易发现，后一组操作可以变成 \text{rot.}\to \text{rev.}，并且相邻两次循环移位操作可以合并。这意味着反转操作一定可以提到最后面。因此进行 k 次的题目所给操作，可以看成是先进行 k 次循环移位操作（每次偏移量是 [1, n-1] 中的一个数），再将序列反转 k 次。

根据反转之前的逆序对数推算反转之后的逆序对数是容易的，接下来讨论如何处理 k 次移位后逆序对数的问题。

我们假设 v_i 表示有多少种方案，使得 k 次移位操作之后，排列相比于初始状态的偏移量为 i（其中 i \isin [0, n-1]）。那么我们断言，对于 v 数组，有

证明

由一次移位的偏移量是 1 \sim n-1，写出 v 数组的 OGF。因为系数对 n 取模，因此 \bmod (1 - x^n) 的意思就是，视 x^n = x^0。

\begin{align} &\space \space \space \space \space \left(x_{n-1} + x_{n-2} + \cdots + x\right) ^ k \bmod (1 - x^n) \nonumber \\ &= \left[\left(x^{n-1} + x^{n-2} + \cdots + 1\right) - 1\right]^k \bmod (1 - x^n) \nonumber \\ &= \sum_{i=0}^k (-1)^{k-i} {k \choose i} \left(x^{n-1} + x^{n-2} + \cdots + 1\right)^i \bmod (1-x^n) \nonumber \\ &= (-1)^k + \sum_{i=1}^k (-1)^{k-i} {k \choose i} \left(x^{n-1} + x^{n-2} + \cdots + 1\right)^i \bmod (1-x^n) \end{align}

考虑

\begin{align} &\space \space \space \space \space \left(x^{n-1} + x^{n-2} + \cdots + 1\right)^2\bmod (1-x^n) \nonumber \\ &= \sum_{i=0}^{n-1} \sum_{j=0}^{n-1}x^{(i + j) \bmod n}\bmod (1-x^n) \nonumber \end{align}

方程 (i + j) \bmod n = k 在 [0, n-1] 的解数，对于 k \isin [0, n-1] 应当都是 n，因为对于每个 i 都有且仅有一个 j 满足这个式子。所以上式

= n\left(x^{n-1} + x^{n-2} + \cdots + 1\right)\bmod (1-x^n)

带回 (1) 可以得到

= (-1)^k + \sum_{i=1}^k (-1)^{k-i} {k \choose i} n^{i-1}\left(x^{n-1} + x^{n-2} + \cdots + 1\right) \bmod (1-x^n)

由这个式子，我们就能注意到，x^1 \sim x^{n-1} 的系数都是相等的，而 x^0 系数相差 (-1)^k。

命题得证。

有了这个结论，我们容易由 \sum\limits_{i=0}^{n-1} v_i = (n-1)^k 求解 X，进而得到 v 数组的值。

那么我们假设 I_i 表示序列循环移位 i 次后，有多少个逆序对。那么

由于是邻项交换，I_0 的变化是容易维护的。考虑如何求出 \sum_{i = 0}^{n-1}I_i。

我们可以枚举数字，看看这两个数字有多少种偏移量能产生逆序对。考虑 p 的逆排列 p^{-1}。对于 x, y (x<y)，能使 x, y 产生逆序对的偏移量个数显然是 (p^{-1}_y - p^{-1}_x) \bmod n。

所求即为

发现 (p^{-1}_j - p^{-1}_i) \bmod n 等于 p^{-1}_j - p^{-1}_i 或者 p^{-1}_j - p^{-1}_i+n，而总共需要 +n 的个数是 p^{-1} 这个序列中的逆序对数。由于每次在 p^{-1} 中交换的都是值域相邻的数，因此这个逆序对数也是好维护的。

接下来我们只需要知道如何维护

一次假设交换 k, k+1，其中 p^{-1}_x = k, p^{-1}_y = k+1，不妨假设 x < y。看一下那些 i, j 的 p^{-1}_j - p^{-1}_i 会有变化：