[Daimayuan] 异或和（C++，异或，数学）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Daimayuan] 异或和（C++，异或，数学）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给定一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ 。请你求出下面式子的模 $1 e 9 + 7$ 的值。

$\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{(a_i\ XOR\ a_j)}}$

输入格式

第一行一个数字 $n$ 。

接下来一行 $n$ 个整数 $a_1,a_2,…,a_n$ 。

输出格式

一行一个整数表示答案。

样例输入

3
1 2 3

样例输出

数据规模

所有数据保证 $2≤n≤300000,0≤a_i<2^{60}$ 。

解题思路

依照题意，我们只能直接跑二重循环（因为 $a_i$ 和 $a_j$ 的组合不会重复，也就是说没有子结构的概念），这肯定会 $T L E$ 。

那么我们考虑异或操作的性质：

异或操作是位操作，无视整个位串的意义，只能看到单个位。——条件（1）

然后重新审视 $\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{(a_i\ XOR\ a_j)}}$ 。

这个式子就是对任意两个元素进行异或操作然后做和，也就是说尝试了所有的组合（ $C_n^2$ ）。——条件（2）

再来看一下异或操作的性质：同则为假，不同为真。——条件（3）

如何利用三个条件优化算法？这里通过一个简单的例子来理解：

有位串 $10000111$ ，我们对任意两个位进行异或操作，然后做和。很容易发现，其和为 $4 * 4 = 16$ 。就是 $1$ 的数量乘上 $0$ 的数量。

然后我们回去看一眼题中的例子：

	1	2	3
1	1	0	1 -> 2 * 1 = 2
2	0	1	1 -> 2 * 2 = 4
4	0	0	0 -> 0 * 4 = 0

比起之前那个简单的例子，也就是多了个权重，仅此而已。

接下来简单说一下代码如何实现：

我们维护每一个位上 $1$ （也可以是 $0$ ）出现的次数；

然后遍历每一个位，累计： $0$ 的数量 $* 1$ 的数量 $*$ 权重。

AC代码如下：文章来源地址https://www.toymoban.com/news/detail-429690.html

#include <iostream>
using namespace std;
const int max_len = 60;
const long long max_a = (1LL << 60LL) - 1LL;
const int max_n = 300000;
const long long mod_num = 1e9 + 7;

long long sum[max_len];

inline void read() {
	long long x, idx = 0;
	cin >> x;
	while (x) {
		sum[idx++] += x & 1;
		x >>= 1;
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) read();
	
	long long ans = 0;
	for (int i = 0; i < max_len; i++) {
		long long power = (1LL << (long long)(i)) % mod_num;
		long long comb = sum[i] * (n - sum[i]) % mod_num;
		ans = (ans + (power * comb) % mod_num) % mod_num;
	}
	cout << ans << endl;
	return 0;
}