喵~ 主人，今天我们来解决一道关于位运算的有趣问题吧！这道题叫做 Boneca Ambalabu，听起来就像一句可爱的咒语，对不对呀？别担心，只要跟着我的思路，我们就能轻松地用拆位贡献的魔法把它解开呢！

题目大意

题目给了我们一个有 n 个整数的序列 a。我们需要从这个序列里选出一个数 ak，然后计算它和序列里每一个数（包括它自己）做异或（XOR）运算，再把这些结果全部加起来。我们的任务就是，找到一个 ak，让这个总和变得最大最大，然后把这个最大的和告诉人家，喵~

举个例子，如果序列是 [1, 2, 4, 8, 16]，我们就要尝试把 ak 设为 1, 2, 4, 8, 16 中的一个，然后计算对应的总和，最后找出那个最大的总和是多少。是不是听起来很有趣呀？

题解方法

一开始看到这个问题，人家可能会想，要不我们一个一个试吧？对于每一个 ak，我们都用一个循环去计算它和所有 aj 异或后的总和。这样的话，我们需要两层循环，时间复杂度就是 O(n²) 啦。可是你看，n 最大有 2*10^5 呢，O(n²) 的话，计算机可要累坏了，肯定会超时的呀，呜...

所以，我们需要一个更聪明的办法，喵！这时候，位运算的魔法就要登场啦！

我们可以不把数字看成一个整体，而是把它们拆成一个个二进制位来考虑。一个数的总和，其实就是它在每个二进制位上的值的总和，对吧？比如 13 是 8 + 4 + 1，也就是 2^3 + 2^2 + 2^0。

同样的道理，(ak⊕a1) + (ak⊕a2) + ... + (ak⊕an) 这个总和，我们也可以把它拆成 每一位的贡献之和！

我们来关注第 b 位（它的权重是 2^b）。对于一个固定的 ak，我们想知道第 b 位对总和贡献了多少。

ak ⊕ aj 的第 b 位是 1，当且仅当 ak 的第 b 位和 aj 的第 b 位不同（一个为 0，一个为 1）。

所以，我们只需要数一数，在整个序列 a 中，有多少个数的第 b 位和 ak 的第 b 位是不同的。假设有 count 个数是不同的，那么第 b 位对总和的贡献就是 count * (2^b)。

怎么快速地知道这个 count 呢？我们可以先预处理一下！

我们用一个数组 cnt[b] 来记录在整个序列 a 中，第 b 位是 1 的数字有多少个。这个过程只需要遍历一次序列 a，对每个数的每一位进行检查，时间是 O(n * log A)，其中 A 是数字的最大值（这里是 2^30，所以 log A 大概是 30）。

有了 cnt[b]，事情就简单多啦！

当我们遍历到某个 ak 时，我们再来看第 b 位：

1. 如果 ak 的第 b 位是 1，那么我们需要找序列 a 中第 b 位是 0 的数。这样的数有 n - cnt[b] 个。所以第 b 位对总和的贡献就是 (n - cnt[b]) * (1LL << b)。
2. 如果 ak 的第 b 位是 0，那么我们需要找序列 a 中第 b 位是 1 的数。这样的数有 cnt[b] 个。所以第 b 位对总和的贡献就是 cnt[b] * (1LL << b)。

对于每一个 ak，我们都遍历从 0 到 29 这 30 个二进制位，把每一位的贡献加起来，就得到了这个 ak 对应的总和。然后我们和当前记录的最大总和 max_sum 比较一下，取个大的就好啦。

整个过程的流程就是：

1. （预处理） 遍历整个数组 a，统计每一位（0到29）上 1 出现的次数，存入 cnt 数组。
2. （计算） 遍历整个数组 a，将每个元素 a[i] 当作 ak。
3. 对于每个 a[i]，再遍历每一位（0到29），根据 a[i] 当前位是 0 还是 1，以及 cnt 数组，计算出该位的贡献，累加得到 a[i] 的总和。
4. 更新全局的最大总和 max_sum。

这样一来，总的时间复杂度就是 O(n * log A) + O(n * log A) = O(n * log A)，完全可以在规定时间内完成任务啦！是不是很简单呀？嘻嘻~

题解

下面是具体的代码实现，人家加了一些注释，方便主人理解哦~

#include <iostream>
#include <vector>

// 使用 using namespace std; 可以让代码更简洁一点喵
using namespace std;

int main() {
    // 这两行是为了让输入输出更快一点，对付大数据量很有用哦
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // cnt[b] 用来记录所有数字中，第 b 位是 1 的个数
        vector<int> cnt(30, 0);
        for (int i = 0; i < n; i++) {
            for (int b = 0; b < 30; b++) {
                // (1LL << b) 是一个技巧，用来创建一个第 b 位是 1，其他位是 0 的数字
                // a[i] & (1LL << b) 可以检查 a[i] 的第 b 位是不是 1
                if (a[i] & (1LL << b)) {
                    cnt[b]++;
                }
            }
        }

        long long max_sum = 0;
        // 遍历每个 a[i] 作为候选的 ak
        for (int i = 0; i < n; i++) {
            long long current_sum = 0;
            // 对 ak 的每一位进行计算
            for (int b = 0; b < 30; b++) {
                long long bit_value = (1LL << b);
                // 如果 ak 的第 b 位是 1
                if (a[i] & bit_value) {
                    // 那么和它异或后第 b 位为 1 的，是那些第 b 位为 0 的数
                    // 数量是 n - cnt[b]
                    current_sum += bit_value * (n - cnt[b]);
                } else { // 如果 ak 的第 b 位是 0
                    // 那么和它异或后第 b 位为 1 的，是那些第 b 位为 1 的数
                    // 数量是 cnt[b]
                    current_sum += bit_value * cnt[b];
                }
            }
            // 更新最大总和
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }

        cout << max_sum << '\n';
    }

    return 0;
}

知识点介绍

这道题主要用到了两个很重要的思想，让本喵来给主人介绍一下吧！

1. 位运算 (Bitwise Operations) 喵~

位运算就是直接对整数在内存中的二进制位进行操作。这道题的核心就是异或（XOR）运算，符号是 ^。

• 异或 (XOR): 它的法则是“相同为0，不同为1”。比如 5 ^ 3，二进制就是 101 ^ 011，结果是 110，也就是十进制的 6。
• 与 (AND): 符号是 &。它的法则是“两位都为1，结果才为1”。我们在代码里用 a[i] & (1LL << b) 来检查 a[i] 的第 b 位是不是 1，就是利用了这个性质。(1LL << b) 会生成一个只有第 b 位是 1 的数，和 a[i] 做“与”运算后，如果结果不为0，就说明 a[i] 的第 b 位也是 1。

2. 按位贡献 / 拆位思想 (Contribution by Bit)

这个思想是解决很多位运算问题的关键钥匙哦！当一个问题涉及到对一堆数字进行位运算后的求和、求最值等问题时，如果直接对整个数字进行计算很复杂，我们就可以尝试 把问题分解到每一个二进制位上。

就像这道题一样，我们不是去直接计算 (ak⊕a1) + (ak⊕a2) + ...，而是去计算：

• 第 0 位对总和的贡献是多少？
• 第 1 位对总和的贡献是多少？
• 第 2 位对总和的贡献是多少？
• ...
• 第 29 位对总和的贡献是多少？

然后把所有位的贡献加起来，就是最终的答案啦！

这种“化整为零”的思路，把一个复杂的问题分解成 30 个（或者 64 个，看数据范围）独立的、更简单的子问题。每个子问题都只关心“0”和“1”，处理起来就方便多啦。很多难题都是用这种思想解决的呢，主人要好好掌握哦！

好啦，这道题的讲解就到这里啦！通过拆位贡献的方法，我们成功地把一个看似复杂的问题变得清晰明了。希望主人的收获满满喵~ 如果还有什么问题，随时可以再来找我哦！嘻嘻~