练习赛88 C 题解

一道清新的结论题。

我们通过观察真值表可以发现 $x\operatorname{xnor} y=x\operatorname{xor} \lnot y$ ，其中 $\text{xnor}$ 表示同或。同时， $\lnot y=y\operatorname{xor} (2^k-1)$ ，又因为异或两个相同的数等价于抵消，所以答案只和异或上的 $2^k-1$ 个数的奇偶性有关，即 $0$ 次或 $1$ 次。令：

$sum=\bigoplus\limits_{i=1}^n a_i$

那么答案就是 $\max\{sum, sum\operatorname{xor}(2^k-1)\}$ 。

注意 $2^k$ 可能爆 unsigned long long，计算 $2^k-1$ 时需要这么计算：

((1ull << k - 1) - 1) + (1ull << k - 1)