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

前言：考场上使用神秘的样例分析法蒙出来了，赛后发现竟然被评了个紫，万恶的良心驱使我写一篇题解。

---

我们先看到操作。

1. 任选一个数字使其 \(+2\)
2. 选择两个相邻的数字使其各 \(+1\)

要求 使用操作 \(2\) 的次数最小。

换句话说我们可以任意使用操作 \(1\) 。

这启发我们进行 奇偶性分析。

对于一个奇数 \(n\) ， \(1-n\) 的排列中奇数的个数为 \(\frac{n+1}{2}\) 。令其等于 \(k\) .

我们对于一个排列\(\pi\)，构造它 \(\bmod 2\) 意义下的数列 \(b\)

\[(\pi_1 \bmod 2,\pi_2 \bmod 2,...\pi_n \bmod 2 ) \]

我们不妨称此为一次映射。

对于一组 \(b\) ，在所有排列中由此映射到这个 \(b\) 的个数都是

\[k!\times (n-k)! \]

事实上，我们发现，对于映射后序列相同的所有排列，其答案必然相等。

我们记 \(S_b\) 表示 \(b\) 中为 \(1\) 的位置的下标的集合。显而易见 \(|S_b| = k\)

我真没在骂人

记 \(m(S_b)\) 表示 \(S_b\) 这个代表的所有排列的答案。

则

\[ans= k!(n-k)! \Sigma_{|S_b|=k}m(S_b) \]

记 \(C=(^n_k)\)，则

\[ans=n!\frac{1}{C} \Sigma_{|S_b|=k}m(S_b) \]

---

此时问题转化为如何求这个操作次数。

• 给定一个奇偶向量 \(b=(b1,\dots,b_n)\)

我们将 操作转化为线性方程

把在第 \(i\) 条边（即连接顶点 i 与 i+1 ）所做操作 (2) 的次数记为整数 \(x_i\ge0\) \((i=1,\dots,n-1)\)。

每次操作在两个相邻位置同时 +1，因此只改变这两个位置的奇偶（翻转）。

若我们只关心 模 2 的奇偶，则每个顶点的最终奇偶等式为（以目标统一成常数 \(t\in{{0,1}}\)，表示我们要把全部数变成偶或全部变成奇）：

\[ x_{i-1}+x_i \equiv b_i + t \pmod 2\quad (i=1,\dots,n), \]

其中约定 \(x_0=x_n=0\).

你现在发现这个 \(t\) 很烦人。我们随机手算一下样例会发现这个 \(t\) 其实是 唯一确定的 ！

考虑由 GPT 提供的证明。

将 RHS 总和求和得到

\[\Sigma_{i=1}^n(b_i+t)=\Sigma b_i +nt=k+nt \]

左式 必定为偶数，因此 \(t\) 与 \(k\) 同奇偶

\[\square \]