P14321 解题报告

· · 题解

前言

咋这么多拉马努金，唉，这东西猫猫真看不出来啊。

但推式子啥的很自然吧，甚至可以不推式子，感觉 gold 老师这题很好喵。

思路分析

首先一些基础的观察和注意。

注意到操作 1 可以让所有奇偶性相同的数字都变相同，而操作 2 是改变两个相邻数字的奇偶性。

所以我们不妨直接将所有数对 2 取模，这样得到的序列就会变成：

1,0,1,1,0,0,1,0,0,0,1,\dots

这样的状物。

然后我们考虑下怎么去消这个东西。

首先我们要确定哪一种是偶数个，是偶数个 0 还是偶数个 1。

因为我们每次操作改变两个数的奇偶性，所以 0,1 数量的变动都是偶数，只有偶数的能消完。

这个其实是不影响问题的，我们不妨钦定现在 1 有偶数个，然后我们要去把这些 1 消掉变成 0。

像是这样一个序列：

1,0,1,0,1,0,0,1

我们注意到一次操作，如果操作在 11 上，那么就是将他们都变成 0（消掉）。

如果是操作在 01 上，就相当于把 1 左移一位变成 10，10 同理。

那么对于上面这个序列的情况，我们最优的策略是：找到当前第一个存在的 $1$，操作 $10$ 或者 $11$（就是直接操作他这一位肯定最优）。 这个是为什么呢？ 这样的话我们相当于是把所有的 $1$ 拿出来，第 $2i-1$ 个和第 $2i$ 个配对。 这样肯定是最优的，证明我们考虑如何表示操作次数。 假设从左往右第 $i$ 个 $1$ 的位置为 $p_i$。 那么我们这样方案的总步数就是 $\sum\limits_{i=1}^{\frac{n}{2}} p_{2i}-p_{2i-1}$，其中 $n$ 为 $1$ 的个数。 然后对于这个东西，我们考虑类似于一个排序不等式的思想，扰动一下他，随意交换两项。 因为这个操作的性质所以我们这配对的必须要是符合括号匹配的配对。 比如 $1,1,1,1$，你无法做到 $1,3$ 位置的配对，$2,4$ 位置的配对，这相当于括号序列 `(())`，真实配对为 $1,4$ 和 $2,3$。 比如我们本来是 $(2i-1,2i),(2j-1,2j),(i<j)$。 然后我们交换成为了 $(2i-1,2j),(2i,2j-1),(i<j)$。 然后我们算一下 $\Delta=2p_{2j-1}-2p_{2i}$，因为 $p_i<p_{i+1},2j-1>2i$，所以显然是劣的。 也就是说肯定是从左往右匹配最优了。 然后这样转化完了之后我们来考虑算贡献。 这个东西其实挺难数的，还是需要一些关键的转化。 首先有 $n$ 个 $1$，我们至少需要操作 $\frac{n}{2}$ 步，这个是浅显易懂的。 接下来我们考虑什么样的情况会让操作次数变多？或者说，我们来考虑拆贡献这样。 那就是 $0$ 放在 $1$ 中间。 具体的呢，我们注意到应该是 $0$ 夹在配对的一对 $1$ 中间就会有 $1$ 的贡献。 然后我们的问题就变成了怎么去数这样的 $0$ 的总数。 假设 $10$ 总数为 $n$，$1$ 总数为 $m$。 首先 $1$ 之间和 $0$ 之间是可以任意排列的，所以方案数为 $m!(n-m)!$。 注意到呢，$m$ 个 $1$ 能产生 $\frac{m}{2}$ 对，有贡献的空为 $\frac{m}{2}$ 个，总空数量为 $m+1$ 个。 然后插板法我们知道这样的总方案数为 $\binom{(n-m)+(m+1)-1}{n-m}=\binom{n}{m}$。 然后我们不妨考虑一个空的期望贡献是多少，那就是每个 $0$ 都有 $\frac{1}{m+1}$ 的概率命中这个空，期望贡献就是 $\frac{n-m}{m+1}$。 然后对于所有有贡献的空都是这样的，所以再乘上去，就得到了 $\frac{m}{2}\binom{n}{m+1}$。 最后一步是一个吸收恒等式，把 $\frac{n-m}{m+1}$ 放进去了，但其实也没必要，单纯为了写的好看。 这整个过程是非常自然的也完全用不着推式子。 从本质而言相当于我们用组合意义将范德蒙德卷积直接证明了一遍，所以没有用到范德蒙德卷积来推这个东西了。 最后的式子就是 $\frac{m}{2}n!+m!(n-m)!\frac{m}{2}\binom{n}{m+1}$，对于 $0$ 为偶数个的情况你反过来自己推一下也是简单的，就不再赘述了。 ## 代码 代码没什么好看的，反正都是两行的东西。