Codeforces Round #717 AGAGA XOOORRR - 二进制

题意

给你一个长度为$n$的数组$a$。现在每一步你可以选择相邻两个数，删除这两个数，并将这两个数的异或放在这两个数原来的位置。问：是否可能通过一系列操作使数组中剩下的所有数都一样且剩下的数组长度至少为2。

题解

首先，如果所有数的异或和为0。那么必然是可以的。因为当且仅当$a[1]\oplus a[2]\oplus...\oplus a[n-1]=a[n]$时，其异或和为0。于是我们得到最终满足要求的数组为：$(a[n], a[n])$。

所以剩下的问题是，当异或和不为0的时候怎么办。

假如$a[1]\oplus a[2]\oplus...\oplus a[n-1]\oplus a[n]=x$，且假设能够构建出题目要求的数组，那么构造出来的结果必然是$(x,x,x,...,x)$。那么必然存在这样的$i$，使得$a[i]\oplus a[i+1]\oplus ... \oplus a[n-1]\oplus a[n]=x$，且$a[1]\oplus a[2]\oplus ... \oplus a[i-1]=0$。

因此最后的问题就是从0到$i-1$的最后若干位中，是否能构造出$x$。如果能，可以构造出$(x,x,x)$。否则就不可能。

代码