题解 | #圣#_牛客博客

原始问题要求计算如下表达式的值：

$\text{Ans} = \bigoplus_{i=1}^{n} \left( \bigvee_{j=1}^{n} (a_i \land a_j) \right)$

直接模拟上述过程需要两层嵌套循环，时间复杂度为 $O(N^2)$ 。鉴于 $\sum N \le 5 \times 10^5$ ，平方级算法会导致超时（运算量可达 $10^{10}$ 级别）。因此，必须在数学层面进行简化。

逻辑推导 让我们聚焦于内层循环计算的临时变量 $tp_i$ ：

$tp_i = \bigvee_{j=1}^{n} (a_i \land a_j)$

其中 $\bigvee$ 表示按位或（OR）， $\land$ 表示按位与（AND）。

利用布尔代数的 吸收律（Absorption Law）：对于任意数值 $A$ 和 $B$ ，恒有 $A \lor (A \land B) = A$ 。具体的推导逻辑如下：

子集性质：对于任意 $j$ ， $(a_i \land a_j)$ 的结果中的二进制位为 $1$ 的位置，必然也是 $a_i$ 中为 $1$ 的位置。换句话说， $(a_i \land a_j)$ 的二进制位总是 $a_i$ 的子集。
自身包含性：循环变量 $j$ 的取值范围是 $1$ 到 $n$ ，其中必然存在一次 $j=i$ 的情况。此时该项为 $(a_i \land a_i) = a_i$ 。
最终值：

$tp_i = (a_i \land a_1) \lor (a_i \land a_2) \lor \dots \lor (a_i \land a_i) \lor \dots \lor (a_i \land a_n)$

由于其中包括了项 $a_i$ ，且其他所有项 $(a_i \land a_j)$ 经过“或”运算后都不会增加 $a_i$ 中不存在的 $1$ 位（它们被 $a_i$ “吸收”了）。因此，我们可以得出结论：

$tp_i = a_i$

结论原问题等价于求数组中所有元素的异或和：

$\text{Ans} = \bigoplus_{i=1}^{n} a_i$

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        ll sum = 0LL;
        for (int i = 0; i < n; i++) {
            ll a;
            cin >> a;
            sum ^= a;
        }
        cout << sum << endl;
    }
}