题解：AT_arc080_d [ARC080F] Prime Flip

· · 题解

距离我 AC 此题已经 6 年了，其它题解对做法已经说得够清楚了，但我发现大家都绕过了一个关键逻辑。

其它题解的问题

首先，令 b_i=a_i\;\text{xor}\;a_{i-1}，得到一个包含偶数个 1 的数组 b。接下来我们称 (i,j) 为一个令 b_i 和 b_j 同时反转的 操作 ，满足 ：|i-j| 是奇质数（以下简称“操作”）

所有题解都提到，我们要让 b_i=b_j=1 的位置两两配对消去，消去的代价可能为 1、2 或 3，于是求解分为三步：

在默认两两配对消去的前提下，显然上述方法是最优解。但是，但是，但是！ 但是我们跳过了一个关键的思考步骤：为什么一定是两两配对消去？

这不是一个显然的问题。

解决这个问题

定义：如果一个操作序列一共有 k 步，最终效果是消除 b 中的两个 1 且不引入额外的 1，我们就称之为 G_k 序列。

引理： 如果一个操作序列消去了 b 中 m 个 1，且最后没有产生新的 1，那么 m 一定是偶数。（这是显然的）

定理：如果一个长为 k 的操作序列 F 消去了 b 中 m 个 1，且最后没有产生新的 1，且 k<m，那么序列中一定包含一个操作 (i,j)，满足：b_i 和 b_j 本来就是 1.

证明： 考虑任意一个操作 (i,j)，可能会令：

我们用反证法，如果一个满足定理条件的操作序列中不包含一个操作 (i,j)，满足：b_i 和 b_j 本来就是 1.

假设 c_3=0 ，那么 c_1 和 c_2 唯一确定，且必然有 c_1>c_2，这意味着 b 中至多出现 c_2 个新的 1，在反证假设下，第一种操作不能选择两个老的 1，第一种操作只能作用于（新1-老1）或（两个新 1）的配对，而这些配对至多 c_2 个，但我们需要至少 c_1 个，与 c_1>c_2 矛盾。

现在 假设 c_3>0 ，那么设上一个假设中三个数的值为 c_1',c_2',c_3'。 第一种操作显然不能减少，只能令 c_2=c_2'-2p，c_1=c_1'+p，c_3=p。此时 c_1>c_1'>c_2'。

这意味着 b 中至多出现 c_2+2c_3=c_2' 个新的 1，而第一种操作不能作用于两个老 1，只能作用于（新1-老1）或（两个新 1）的配对，而这些配对至多 c_2' 个，但我们需要至少 c_1 个，与 c_1>c_2' 矛盾。

推论：根据上述定理，一个满足定理条件的操作序列一定可以被拆分成两个序列：

假如 F' 仍然满足定理条件，可以继续拆分，直到 k=m 为止。此时剩余的序列和两两配对消去具有一样的代价。因此整体上看，任何一个 k<m 的操作序列一定和一系列 G_1 序列+一系列 G_2 序列具有一样的效果。

因此，默认两两配对消去，并贪心令代价为 1 的操作尽可能多，一定能找到最优解。