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$。

标签: 位运算, 构造

添加新评论