喵哈~！各位算法大师们好呀！我是你们的小助教猫娘，今天也要元气满满地解决问题喵！(ฅ'ω'ฅ)
这次我们要挑战的是一道关于位运算的数学题，叫做“阿波罗对决潘神”。听起来就好厉害的样子！不过别怕，只要跟着本猫娘的思路，再复杂的题目也会变得像毛线球一样好玩哦~
题目大意
我们拿到一个有 n 个非负整数的序列 x1, x2, ..., xn。
任务是计算下面这个看起来超——级复杂的公式的值：
这里的 & 是按位与（AND），| 是按位或（OR）。
因为结果可能会非常大，所以我们需要把最终答案对 10^9 + 7 取模。
简单来说，就是三重循环，把每一组 (i, j, k) 对应的 (xi & xj) * (xj | xk) 的值都加起来。但是 n 最大有 5 * 10^5，三重循环的话，复杂度是 O(n^3)，肯定会超时的喵！所以我们需要找到更聪明的办法才行。
题解方法
看到这种三重求和，我们的第一反应就是要想办法把它拆开，简化计算，不然电脑会累坏的，就像追着激光笔跑了一整天的猫咪一样，呜...
我们来仔细观察一下这个公式：
注意到 i 和 k 的求和是相互独立的，它们都只和 j 有关。所以我们可以把 j 的求和提到最外面，然后把和 i 相关的部分以及和 k 相关的部分分开来，喵~
公式可以变形为：
这样一来，问题就变成了对于每一个 j（从 1到 n），我们计算两个部分：
A_j = ∑(i=1 to n) (xi & xj)B_j = ∑(k=1 to n) (xj | xk)
然后最终的答案就是 ∑(j=1 to n) (A_j * B_j)。
虽然看起来好了一点，但对于每个 j，计算 A_j 和 B_j 仍然需要 O(n) 的时间，总复杂度还是 O(n^2)，还是不够快呀！得再动动我们的小脑袋瓜~
关键思路：按位拆解！
数字的位运算问题，通常的必杀技就是把数字拆成二进制的每一位来单独考虑贡献！因为 xi 最大是 2^60 - 1，所以我们只需要考虑 0 到 59 这 60 个二进制位。
如何计算 A_j？
A_j = ∑(i=1 to n) (xi & xj)
xi & xj 的值，等于它在二进制下每一位的贡献之和。也就是说，如果 xi & xj 的第 b 位是 1，它对总值的贡献就是 2^b。
A_j = \sum_{i=1}^{n} \sum_{b=0}^{59} \text{bit}_b(x_i \ \& \ x_j) \cdot 2^b
其中 bit_b(N) 表示数字 N 的第 b 位是 0 还是 1。
我们可以交换求和顺序： A_j = \sum_{b=0}^{59} 2^b \cdot \left( \sum_{i=1}^{n} \text{bit}_b(x_i) \ \& \ \text{bit}_b(x_j) \right)
对于固定的 j 和位 b：
- 如果
xj的第b位是 0，那么bit_b(xi) & 0永远是 0。 - 如果
xj的第b位是 1，那么bit_b(xi) & 1就等于bit_b(xi)。
所以，∑(i=1 to n) (bit_b(xi) & bit_b(xj)) 的值，就等于所有 xi 中第 b 位为 1 的数字个数！
我们可以预处理一个数组 count[b]，表示输入的所有数字中，第 b 位是 1 的有多少个。这个预处理需要 O(n * 60) 的时间。
于是，A_j 的计算就变成了： A_j = \sum_{b=0, \text{bit}_b(x_j)=1}^{59} count[b] \cdot 2^b
对于每个 j，我们只需要遍历 60 个位，就能算出 A_j，好耶！
如何计算 B_j？
B_j = ∑(k=1 to n) (xj | xk)
直接按位算 | 有点麻烦，我们用一个很棒的恒等式：a | b = a + b - (a & b)。 B_j = \sum_{k=1}^{n} (x_j + x_k - (x_j \ \& \ x_k))B_j = \sum_{k=1}^{n} x_j + \sum_{k=1}^{n} x_k - \sum_{k=1}^{n} (x_j \ \& \ x_k)
这三项分别是：
∑(k=1 to n) xj = n * xj∑(k=1 to n) xk就是所有输入数字的总和，我们记作S_total。∑(k=1 to n) (xj & xk)这个形式是不是很眼熟？它就是我们刚刚算出来的A_j呀！（只是求和变量从i变成了k，本质是一样的）。
所以，B_j = n * xj + S_total - A_j。
总结一下我们的高效算法：
预处理 (O(n * 60))：
- 计算
count[b]数组：对于 0 到 59 的每一位b，统计输入中有多少个数的第b位是 1。 - 计算所有数字的总和
S_total。 - 预计算
2^b的值并取模。
- 计算
主循环 (O(n * 60))：
- 遍历每一个
xj（j从 1 到n）。 - 对于当前的
xj，用O(60)的时间计算出A_j = ∑(b=0, bit_b(xj)=1 to 59) count[b] * 2^b。 - 用
O(1)的时间计算出B_j = n * xj + S_total - A_j。 - 将
A_j * B_j累加到最终答案ans中。 - 记得所有计算都要在模
10^9 + 7下进行哦！
- 遍历每一个
总时间复杂度是 O(n * 60)，对于 n = 5 * 10^5 来说，绰绰有余啦！(๑•̀ㅂ•́)و✧
题解代码
下面就是把上面的思路变成代码啦，本猫娘加了一些注释，方便大家理解每一部分在做什么喵~
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
// 定义模数和二进制位数上限
const int mod = 1000000007;
const int MAX_BIT = 60;
int main() {
// 提高cin/cout效率
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 预计算 2 的幂，避免重复计算
vector<long long> power2(MAX_BIT);
for (int b = 0; b < MAX_BIT; b++) {
power2[b] = (1LL << b) % mod;
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<long long> x(n);
long long total_sum_mod = 0; // S_total
for (int i = 0; i < n; i++) {
cin >> x[i];
total_sum_mod = (total_sum_mod + x[i]) % mod;
}
// 步骤1：预处理 count 数组
vector<int> count(MAX_BIT, 0);
for (int b = 0; b < MAX_BIT; b++) {
long long mask = 1LL << b;
for (int i = 0; i < n; i++) {
if (x[i] & mask) {
count[b]++;
}
}
}
long long final_ans = 0;
// 步骤2：主循环，遍历每个 xj
for (int j = 0; j < n; j++) {
// 计算 A_j
long long term_A = 0;
for (int b = 0; b < MAX_BIT; b++) {
// 如果 xj 的第 b 位是 1
if (x[j] & (1LL << b)) {
// 贡献是 count[b] * 2^b
long long contribution = (power2[b] * count[b]) % mod;
term_A = (term_A + contribution) % mod;
}
}
// 计算 B_j
long long term_B = 0;
for (int b = 0; b < MAX_BIT; b++) {
long long contribution;
// 如果 xj 的第 b 位是 1
if (x[j] & (1LL << b)) {
// 这一位上，xj | xk 的结果总是 1
// n 个 xk 中，这一位都是 1，所以总贡献是 n * 2^b
contribution = (power2[b] * n) % mod;
} else { // 如果 xj 的第 b 位是 0
// 这一位上，xj | xk 的结果取决于 xk
// 贡献是 count[b] * 2^b
contribution = (power2[b] * count[b]) % mod;
}
term_B = (term_B + contribution) % mod;
}
// 累加 A_j * B_j 到最终答案
final_ans = (final_ans + (term_A * term_B) % mod) % mod;
}
cout << final_ans << endl;
}
return 0;
}代码说明喵: 上面的代码中计算 B_j 的方法和我们推导的 B_j = n * xj + S_total - A_j 不太一样，但本质是等价的，都是按位计算。让我们看看代码里的 B_j 是怎么算的：
B_j = ∑(k=1 to n) (xj | xk) = ∑(b=0 to 59) 2^b * (∑(k=1 to n) bit_b(xj | xk))
- 如果
xj的第b位是 1，那么xj | xk的第b位也一定是 1，不管xk的第b位是啥。这种情况有n次，所以贡献是n * 2^b。 - 如果
xj的第b位是 0，那么xj | xk的第b位就等于xk的第b位。贡献就是count[b] * 2^b。
两种方法都可以得到正确的结果，用公式 B_j = n * xj + S_total - A_j 会让代码更简洁一些，就像题解给出的参考代码一样。两种方法都展示了位运算问题的核心思想，非常棒！
知识点介绍
这道题用到了几个非常基础但重要的知识点，本猫娘来给大家梳理一下~
位运算 (Bitwise Operations)
- 按位与 (
&): 两个二进制数的同一位都为 1 时，结果的该位才为 1，否则为 0。比如5 (101) & 3 (011) = 1 (001)。我们常用x & (1LL << b)来判断x的第b位是否为 1。 - 按位或 (
|): 两个二进制数的同一位只要有一个为 1，结果的该位就为 1。比如5 (101) | 3 (011) = 7 (111)。
- 按位与 (
模运算 (Modular Arithmetic)
- 在算法竞赛中，当结果可能非常大，超过
long long的范围时，题目通常会要求对一个大质数（比如10^9 + 7）取模。 - 基本性质：
(a + b) % m = ((a % m) + (b % m)) % m(a * b) % m = ((a % m) * (b % m)) % m(a - b) % m = ((a % m) - (b % m) + m) % m（减法要加上m再取模，防止出现负数）
- 在算法竞赛中，当结果可能非常大，超过
公式推导与化简
- 这是解决许多数学和计数问题的关键。面对复杂的求和或乘积公式，不要害怕，尝试：
- 交换求和顺序：像我们把
j的求和提到最外面一样。 - 利用恒等式：比如
a | b = a + b - (a & b)。 - 拆分贡献：比如按位拆分，将一个复杂数字的贡献拆成每一位的贡献之和。
- 交换求和顺序：像我们把
- 这是解决许多数学和计数问题的关键。面对复杂的求和或乘积公式，不要害怕，尝试：
好啦，今天的讲解就到这里啦！希望大家都能理解并掌握这个问题的解决方法。以后遇到类似的题目，也要像小猫咪一样，用敏锐的直觉找到问题的突破口哦！喵~ (ฅ^•ﻌ•^ฅ)