题解：P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds

首先考虑对于一个给定排列

p

的最优策略：

我们有以下观察：
注意到第一种操作不限次数，可以让某个数在奇偶性不变的情况下成为与之奇偶性相同的任何数，那么我们可以把原来排列中奇数看成 $1$ ，偶数看成 $0$ ，这样方便我们操作。
对于二操作，如果是对于一个 $\left < 0,1\right >$ 之间的操作，那么等价于交换这两个数，否则等价于两个数取反，由于交换两个数并不会影响 $0,1$ 的数量，而且取反总会让两个取反，而排列的长度是奇数，所以一定是有偶数个元素的数最后取反若干次，最后全部成为之前有奇数个元素的数。
而对于需要取反的数，我们自然想到一个贪心的解法就是从前往后两两匹配，每一组的代价就是这两个位置之间另一个元素的出现次数，当前别忘记最后加上取反的次数，也就是偶数个元素出现个数的一半。

那么我们就可以枚举两两匹配时中间不同的元素的总个数，称为

j

，再设

\text{match}

表示需要最后两两匹配的元素个数，

\text{notmatch}

为最后不两两匹配的元素个数，显然一个元素要么是匹配的要么不匹配，所以

\text{match} + \text{notmatch} = n

。

那么对于我们确定了最后的代价

j

后，我们需要把这

j

个数插入到任意某个组的两个位置中间，由于一共有

\frac{\text{match}}{2}

组，所以相当于求方程：

\sum_{i = 1} ^ {\frac{\text{match}}{2}} x_i = j,x_i \ge 0

解的数量，根据插板法，这个式子可以化简为：

\binom{j + \frac{\text{match}}{2} - 1}{\frac{\text{match}}{2} - 1}

而对于除去这

j

个数后的另外

\text{notmatch} - j

个数，它们要插入到这

\frac{\text{match}}{2}

个组的

\frac{\text{match}}{2} + 1

个空隙中，这个还是求方程的解的问题，可以化简为：

\binom{\text{notmatch} - j + \frac{\text{match}}{2} + 1 - 1}{\frac{\text{match}}{2} + 1 - 1} = \binom{\text{notmatch} - j + \frac{\text{match}}{2}}{\frac{\text{match}}{2}}

所以答案就是对于每个

j

求和再乘上阶乘再加上每种情况都有的贡献：

n ! \cdot \frac{\text{match}}{2} + \text{match}! \cdot \text{notmatch}!\cdot \sum_{j = 0} ^ {\text{notmatch}} \binom{j + \frac{\text{match}}{2} - 1}{\frac{\text{match}}{2} - 1} \cdot \binom{\text{notmatch} - j + \frac{\text{match}}{2}}{\frac{\text{match}}{2}}

此时期望得分为

\green{87}

分。

在这里，由于带着

\text{match}

不是很好看，我们用

q = \text{notmatch},p = \text{match},k = \frac{p}{2}

，由于固定的贡献是好

\mathcal O(V) \sim \mathcal O(1)

计算的，所以我们暂且只考虑后面带

\sum

的式子如何化简。

首先替换变量后原式得：

\sum_{i = 0} ^ q i\cdot \binom{i - 1 + k}{k - 1} \cdot \binom{q - i + k}{k}

把组合数的第一个展开成阶乘的形式得到：

\binom{i - 1 + k}{k - 1} = \frac{(i - 1 + k) ! }{(k - 1) ! \cdot i!}

所以：

\binom{i - 1 + k}{k - 1} \cdot i &= \frac{(i - 1 + k) ! }{(k - 1) ! \cdot i!} \cdot i \\ &= \frac{(i - 1 + k)!}{(k - 1)!\cdot (i - 1)!} \\ &= \frac{(i - 1 + k)! \cdot k}{k! \cdot (i - 1)!} \\ &= k \cdot \binom{i - 1 + k}{k} \end{align*}$$ 所以原式得： $$\sum_{i = 0} ^ q k\cdot \binom{i - 1 + k}{k} \cdot \binom{q - i + k}{k}$$ 由于： $$\sum_{i} \binom{p - i}{x} \cdot \binom{q + i}{y} = \binom{p + q + 1}{x + y + 1}$$ 所以我们把： $$k - 1 \rightarrow q,q + k \rightarrow p$$ 则原式得： $$k\cdot \binom{k - 1 + q + k + 1}{2k + 1} = k\cdot \binom{2k + q}{2k + 1} = k\cdot \binom{p + q}{p + 1} = k\cdot \binom{n}{p + 1}$$ 所以答案就是： $$k\cdot \binom{n}{p + 1} + n! \cdot k$$ 时间复杂度容易做到 $\mathcal O(V + T)$。 ~~代码是个人都会写~~，不给了。

文章操作