题解：P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds
xxr___
·
·
题解
首先考虑对于一个给定排列 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)。
代码是个人都会写，不给了。