ARC080F Prime Flip 题解

传送门

题意：给定初始 \(a\) 数组，每次可以选一个长度为奇质数的区间取反。问全变成 \(0\) 要多少次操作。

和 Password、Xor Replace 的套路相同，做一个差分。

令 \(b_i=a_i\xor a_{i-1}\)，目的就是让 \(b\) 数组变为全 \(0\)。对 \(a_i\sim a_{i+p-1}\) 取反相当于对 \(b_i,b_{i+p}\) 取反。显然 \(b\) 中有偶数个 \(1\)。

一次操作可以让 \(b_i,b_j\) 取反，要求 \(j-i\) 是奇质数。

最终的操作可以看作把 \(b\) 中所有 \(1\) 两两匹配，然后每一对 \(1\) 消耗若干次操作变成 \(0\)。

考虑两个位置 \(i,j\) 需要多少次操作才能一起变 \(0\)。

1. \(j-i\) 为奇质数。显然一次即可。

2. \(j-i\) 为大于 \(4\) 的偶数。根据哥德巴赫猜想：大于 \(4\) 的偶数可以分成两个奇质数之和。 所以两次即可。一次显然不够，因为加一个奇质数后奇偶性不对。

3. \(j-i\) 为奇合数，\(3\) 次操作。一次操作变回 \(2\) 的情况。

4. \(j-i=2\) 或 \(j-i=4\)。对于 \(j-i=2\)，因为 \(2=5-3\)，两次；\(j-i=4\)，因为 \(4=7-3\)，两次。不如把该情况和情况 \(2\) 合并。

要操作次数最少，显然尽量选择情况 \(1\)（\(1\) 也不会干扰到情况 \(2,3\)）。

于是把 \(b\) 中所有 \(1\) 的位置找出来，分成奇数偶数的二分图。如果两个位置差为奇质数，连边。

先求个最大匹配，就是情况 \(1\) 的个数。然后让奇数偶数各自内部尽量匹配，对应情况 \(2\)。最后让剩下的奇数偶数之间匹配，对应情况 \(3\)。