题解：P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds
hahasha
·
·
题解
结论题，设 x = \frac{1}{2}\times \operatorname{round}(\frac{n}{2})，其中 \operatorname{round} 为向最近偶数取整，则答案为 (n + 1)! \times \frac{x}{2x + 1}。
先不妨假设 n 是 4k + 3 型奇数。
考虑原序列的前缀和 \bmod 2 数组，容易发现操作是将任意一个非最后的位置取反。因为 \frac{n(n + 1)}{2} 为偶数，所以最终每一项都应当是偶数。因此一个这样的序列方案数就是其中 1 的个数。
因为我们只用保留奇偶性，所以不妨把排列变为 \frac{n - 1}{2} 个 0 和 \frac{n + 1}{2} 个 1，最后答案乘上 (\frac{n - 1}{2})!(\frac{n + 1}{2})! 即可。
前缀和一下，就变成了有 \frac{n + 1}{2} 个位置与上一个不同（假设第 0 位为 0），要数 1 的个数。自然想到 dp。
设 f_{i, j} 表示前 i + j 位中，（原序列）有 i 个 0 和 j 个 1 的贡献之和，则：
f_{i, j} = f_{i - 1, j} + f_{i, j - 1} + (j \bmod 2) \times \binom{i + j}{j}
观察这样的转移路径（下图为 n =7）：
从左下角开始，每次只能往右、上，如果走的是红边就要加上一个组合数。
其实组合数就是从原点走到 (i, j) 的方案数，所以答案就是所有左下到右上的路径经过的红边的数量和。
可以发现竖着的红边是一定要走的，而横着的边，相当于一个插板法。假设横着的一共要走 s 步，一共有 l 条横着的黑线，r 条横着的红线，则我们相当于要把 s 步分摊到 l + r 条线上，可以得到以下的式子：
\begin{aligned}
\text{Ans} &= \sum_{y =0}^s (y + r) \binom{s - y + l - 1}{l - 1} \binom{y + r - 1}{r - 1}\\
&= \sum_{y=0}^s r\binom{y + r}{r}\binom{s - y + l - 1}{l - 1}
\end{aligned}
会推组合数的就很容易。不会的话可以发现，这个形式就是一个卷积。我们有 \frac{1}{(1-x)^{r + 1}} = \sum x^i \binom{i + r}{r}，所以原式就是 \frac{1}{(1 - x)^{l + r + 1}} 的第 s 项，即：
\text{Ans} = r \times \binom{s + l + r}{l + r}
记得乘上前面的两个阶乘。现在我们来算一下 s, l, r。容易发现 s = \frac{n - 1}{2}，r = \frac{n + 1}{4}, l = r + 1，因此答案为：
\begin{aligned}
&\frac{n + 1}{4} \times \frac{(n + 1)!}{(\frac{n - 1}{2})!(\frac{n + 1}{2} + 1)!} \times (\frac{n - 1}{2})! \times (\frac{n + 1}{2})!\\
=& (n + 1)! \times \frac{\frac{n + 1}{4}}{\frac{n + 1}{2} + 1}
\end{aligned}
当 n 是 4k + 1 型奇数时，最终每一项都要是奇数。因此把奇偶对调一下，就和 4k + 3 型奇数是一样的了。此时可以得到 s = \frac{n + 1}{2}, r = \frac{n - 1}{4}, l = r + 1，因此答案为：
(n + 1)!\times \frac{\frac{n - 1}{4}}{\frac{n - 1}{2} + 1}
可以发现两种情况中 \frac{n \pm 1}{2} 就是 \frac{n}{2} 最接近的偶数，所以就可以得到文章开头的式子了。
代码很好写，就不放了。
以下是 n = 7, 5 的转移图的对比。