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}，则结果为：

m!\cdot (n-m)!\cdot \sum_{i=1}^{n-m} i \cdot \binom{i+b-1}{b-1} \cdot \binom{n-i-b}{b}

直接算是 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}

我们采用以下公式：

\sum_{k} \binom{r-k}{a} \binom{s+k}{b} = \binom{r+s+1}{a+b+1}

为了套用这个公式，我们对求和式 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}

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