题解

思路

数组各位置完全对称。对任意取值 $t$，满足 $a_i=t$ 的好数组数量与位置 $i$ 无关。因此当 $n$ 为偶数时，每种元素贡献都会出现偶数次，答案为零。下文只考虑奇数 $n$，此时答案等于所有好数组中 $a_1$ 的总异或。

异或可逐位统计，只需知道“$a_1$ 的第 $i$ 位为一”的方案数奇偶性。精确要求总 OR 等于 $y$ 不易处理，先计算总 OR 是某个 $s\subseteq y$ 的子集，再在模二意义下做子集容斥；因为 $-1\equiv1\pmod2$，所有容斥项直接相加。

做法

子任务 1：枚举数组

枚举 $y$ 的全部子掩码作为每个 $a_i$，递归生成整个数组，检查元素和与 OR，并把合法数组的 XOR 累计到答案。

子任务 2：枚举允许掩码与首元素

固定允许掩码 $s\subseteq y$ 和首元素 $t\subseteq s$。其余 $n-1$ 个数均为 $s$ 的子掩码且总和为 $x-t$ 的方案数奇偶性，利用 Lucas 定理与 Vandermonde 恒等式等于

二项式系数为奇数当且仅当 $x-t$ 的每个一位都包含在 $(n-1)s$ 中。若成立，就把 $t$ 异或进当前答案。枚举全部二元子集对总复杂度为 $O(3^b)$。

满分做法：消去首元素枚举

统计答案第 $i$ 位时，要求首元素含有 $2^i$。把这一位预先选出，再对所有首元素与其余元素使用 Vandermonde 恒等式合并，可得允许掩码 $s$ 下的方案数奇偶性为

枚举每个 $s\subseteq y$ 以及 $s$ 中每个一位 $2^i$，检查 $x\ge2^i$ 且 $(x-2^i)\subseteq(ns-2^i)$。若成立，就翻转答案第 $i$ 位。

正确性证明

位置对称性保证每个固定元素值在所有位置出现次数相同；把所有数组得分再异或时，偶数 $n$ 的贡献成对抵消，奇数 $n$ 只需保留首位置贡献。

Lucas 定理在模二下说明 $\binom AB$ 为奇数当且仅当 $B\subseteq A$。将“每个元素都是 $s$ 的子掩码”的指示写成二项式系数后，Vandermonde 恒等式把各元素和为 $x$ 的卷积合并为一个二项式系数。对子集 OR 做容斥时正负号在模二下相同，因此枚举全部 $s\subseteq y$ 正确恢复 OR 恰为 $y$ 的奇偶贡献。

中层显式枚举首元素 $t$，满分做法预选目标位并再次用 Vandermonde 合并全部首元素选择，二者统计同一方案集合。每个答案位恰在方案数为奇数时翻转，最终整数就是所有好数组得分的总异或。

复杂度

小层复杂度为 $O(2^{bn})$。

中层时间复杂度为 $O(3^b)$，空间复杂度为 $O(1)$。

满分时间复杂度为 $O(b2^b)$，空间复杂度为 $O(1)$，其中 $b=\operatorname{popcount}(y)\le20$。