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

· · 题解

首先，第一个操作 +2 启发我们只考虑排列数的奇偶性，显然可以把整个序列模 2 考虑，结果不变。

对于一个固定的 n，初始的异或和一定相同，所以所有情况最后都必定是把所有的 0 变成 1 或者把所有的 1 变成 0。

下面分析把所有 1 变成 0 的情况，另一种同理。

设 1 的个数为 a，0 的个数为 b，有 a 是偶数，b 是奇数。对于每一种 01 序列，都有 a!b! 种原排列对应。

考虑贪心，第一个 1 与第二个 1 互相靠近，第三个 1 与第四个 1 互相靠近，以此类推，证明可以用邻项交换法。

设每个 1 的下标为 p_1,p_2,\dots,p_a，则答案为：

\sum_{i=1}^{\frac a2} p_{2i}-p_{2i-1}

令 k=\frac a2，考虑转化成固定 1 的位置，往中间插入 0，注意在两端也能插入，即求

\sum_{x_0+\cdots+x_a=b} \sum_{i=1}^{k} x_{2i-1}+1

考虑先把这个 1 去掉，每一个原排列都有 k 的贡献，对答案的贡献是 kn!。

枚举奇数下标 x 的总和为 m：

\sum_m f(m,k)f(b-m,k+1)m

其中 f(n,m) 表示 m 个非负变量和等于 n 的方案数。根据插板法易得 f(n,m)=\binom{n+m-1}{m-1}，代入。

\sum_m m\binom{m+k-1}{k-1}\binom{b-m+k}{k}

我们有 \binom{m+k-1}{k-1}=\frac{(m+k-1)^{\underline{m}}}{m!}=\frac km\binom{m+k-1}{k}（如果你喜欢可以先反转上指标再应用不改变下指标的那个吸收恒等式），所以：

k\sum_m \binom{m+k-1}{k}\binom{b-m+k}{k}

后面这个柿子直接使用上指标范德蒙德卷积（《具体数学》5.26）：

\sum_{-q\le k\le l}\binom{l-k}{m}\binom{q+k}{n}=\binom{l+q+1}{m+n+1}

用 (l,m,n,q)\gets (b+k,k,k,k-1) 代入，就可以得到……

我们需要先解决求和范围的问题：m 的取值范围是 0\le m\le b，但实际上在这个范围之外的 m 都没有贡献，所以可以代入，答案为

k\binom{b+k+k}{k+k+1}

还要把上面的东西乘回来，这里就不给代码了。

注：当 k=0 的时候，不能对 \binom{m+k-1}{k-1} 应用对称恒等式，但没关系。上指标范德蒙德卷积（上面省略了一些限制）可以对两个组合数分别应用对称恒等式再反转上指标来变成范德蒙德卷积。