CF1572B

dottle · 2021-09-21 10:36:21 · 题解

容易发现，在操作前后，三个数的异或和不变。因此有解有一个必要条件：所有数的异或和为 0。

先考虑 n 为奇数的情形，我们依次在 n-2,n-4,...,1 执行一次此操作，此时 a_1=0（即所有数的异或和），其余 a_{2k}=a_{2k+1}；然后我们再依次执行 1,3,...,n-2，这样每次执行都是将一个 0 和两个相同的数变为了 0。

对于 n 为偶数的情形，我们则需要找到一个长为奇数的前缀，使得其异或和为 0，然后依次对这个前缀和剩余部分执行奇数的操作即可。