【题解】CF1438D Powerful Ksenia

CF1438D Powerful Ksenia

给定一个长度为 $n$ 的数组 $a$，现在可以做最多 $n$ 次操作，每次选取三个不同的下标 $i,j,k$，将 $a_i,a_j,a_k$ 都变为 $a_i\oplus a_j\oplus a_k$，其中 $\oplus$ 是异或。求一种方案使得所有数字都相等，或判断不可能。
$3\le n\le 10^5,1\le a_i\le 10^9$。

$\texttt{Solution}$

考虑一下一次操作会对数组产生什么影响。

显然当 $a_i,a_j,a_k$ 相等时没有任何作用。当 $a_i,a_j,a_k$ 互不相等，则他们都会变成一个相同的数字 $a_i\oplus a_j\oplus a_k$。当 $a_i,a_j,a_k$ 中有两个相等，假设是 $a_i=a_j$，那么由于 $a_i\oplus a_j=0$，所以他们三个都会变成 $a_k$。

发现当两个相等时非常好，因为这个变成的数字是可控的。考虑利用这个性质，可以想到将数组变得两两相同。那么对于 $n$ 为奇数的情况，就可以这样构造：

首先对于 $1\le i\le n-2$ 的每一个奇数 $i$，从小到大依次执行 $(i,i+1,i+2)$。不难发现这样操作之后，除了第 $n$ 个之外，前面的两两相等。

然后，再对于 $1\le i \le n-2$ 的每一个奇数 $i$，执行 $(i,i+1,n)$，也就是将 $a_i,a_{i+1}$ 同时变为当前的 $a_n$。这样操作次数是 $n-1$。

再考虑偶数的情形。不难发现上述操作不改变整个序列的奇偶性，又整个序列最后全相等，所以到最后异或和为 $0$。因此先将所有 $a_i$ 异或起来，若不是 $0$ 则无解。否则，我们忽略最后一个 $a_n$，对前 $n-1$ 个值做上述关于奇数的操作，操作完成之后整个序列一定合法。因为异或和为 $0$，所以当前 $n-1$ 个全相等的时候，最后一个也与他们相等！操作次数 $n-2$。