Adjacent Lifting,Fewest Rounds 题解

两年前出的题，自己翻出来的时候做了一个小时，菜干净了。

首先由于有不限次数的操作 $1$，所以我们可以将任意奇偶性相同的数变成同一个数。

于是我们只需要通过最少次数的操作 $2$ 使得所有数的奇偶性相同即可。

首先，我们可以把排列转成 01 序列，所有 01 序列的出现次数显然是相同的。

由于 $n$ 是奇数，所以我们可以唯一确定要把 $0$ 都变成 $1$，还是把 $1$ 都变成 $0$，假设是前者，设 $m$ 为 $0$ 的个数。

考虑对相邻的 01 同时加 $1$ 就是交换它们。

考虑如何确定方案最优，显然将其从左到右按次序两两分为一组，相互靠近，所以，对于一种方案，它所使用的代价就是这样两两分组后，每组的两个 $0$ 之间 $1$ 的个数，再加上 $\frac{m}{2}$。

后者容易解决，直接是 $\frac{m}{2}\cdot n!$，前者考虑枚举这个 $1$ 的总个数 $i$，那么相当于要把 $i$ 个 $1$ 放入 $\frac{m}{2}$ 个段中，剩下的 $n-i-\frac{m}{2}$ 个 $1$ 放入 $\frac{m}{2}+1$ 个段中。

设 $b=\frac{m}{2}$，则结果为：

直接算是 $O(n)$ 的，考虑转一下式子，设 $S=\sum_{i=1}^{n-m} i \cdot \binom{i+b-1}{b-1} \cdot \binom{n-i-b}{b}$。

发现 $i\cdot\binom{i+b-1}{b-1}=b\cdot\binom{i+b-1}{b}$ 。

这是一个关键的变换！现在求和式 $S$ 变成了： $S = \sum_{i=1}^{n-m} b \cdot \binom{i+b-1}{b} \cdot \binom{n-i-b}{b}$ 由于 $b$ 是与 $i$ 无关的常数，我们可以将其提到求和符号外面： $S = b \cdot \sum_{i=1}^{n-m} \binom{i+b-1}{b} \cdot \binom{n-i-b}{b}$

现在我们需要计算这个新的求和式： $S' = \sum_{i=1}^{n-m} \binom{i+b-1}{b} \cdot \binom{n-i-b}{b}$

我们采用以下公式：

为了套用这个公式，我们对求和式 $S'$ 进行换元。令 $j = i-1$，则 $i=j+1$。当 $i$ 从 $1$ 变化到 $n-m$ 时，$j$ 从 $0$ 变化到 $n-m-1$。 $S' = \sum_{j=0}^{n-m-1} \binom{(j+1)+b-1}{b} \cdot \binom{n-(j+1)-b}{b}$ $S' = \sum_{j=0}^{n-m-1} \binom{j+b}{b} \cdot \binom{n-b-1-j}{b}$ 现在这个形式与恒等式 $\sum_{k} \binom{s+k}{b} \binom{r-k}{a} = \binom{r+s+1}{a+b+1}$ 非常接近。

我们来匹配一下参数：

将这些参数代入恒等式的右边： $\binom{r+s+1}{a+b+1} = \binom{(n-b-1) + b + 1}{b+b+1} = \binom{n}{2b+1}$

因此，我们得到了 $S'$ 的封闭形式： $S' = \binom{n}{2b+1}$

于是，不难直接算出答案。