「CF1572B」Xor of 3
给出一个长度为 n 的序列 a,仅由 0 或 1 构成。
你需要对序列进行至多 n 次操作(或者说明这是不可能的),每次操作你可以选择一个下标 i (1 \leq i \leq n - 2),然后将 a_i, a_{i + 1}, a_{i + 2} 均改成 a_i \oplus a_{i + 1} \oplus a_{i + 2}。
数据范围:3 \leq n \leq 2 \times 10^5,0 \leq a_i \leq 1。
时空限制:1s / 256MiB。
Solution
首先注意到,经过一次操作之后,所有数的异或和肯定不变。故有一个必要条件是,所有数的异或和为 0。
当 n 为奇数时,有一个构造:
- 先选择 n - 2, n - 4, \dots, 3, 1 进行操作。此时 a_1 = 0(即所有数的异或和),且 a_{2i} = a_{2i + 1}。
- 再选择 1, 3, \dots, n - 4, n - 2 进行操作。此时每次操作的位置 x 必定满足 a_x = 0, a_{x + 1} = a_{x + 2},故该次操作会使得 a_x = a_{x + 1} = a_{x + 2} = 0。
当 n 为偶数时,考虑找一个长度为奇数,异或和为 0 的前缀,然后对前后缀进行同 n 为奇数情况的构造。
可以证明,若找不到这样的前缀,则一定无解。因为此时原串形如 1aabb..zz1(即首尾均为 1 且 a_{2i} = a_{2i + 1}),不论如何操作仍然有 a_{2i} = a_{2i+1},首尾的 1 无法消掉。