0%

[ABC147D] Xor Sum 4

题目

题目链接

题目大意: 求 $\sum \limits_{i = 1}^{n - 1} \sum \limits_{j = i + 1}^{n} (a_i \text{ xor } a_j)$. $2 \le n \le 3 \times 10^5, 0 \le a_i < 2^{60}$. 结果对 $10^9 + 7$ 取模.

思路

第一次打 ABC 不会做的题.

一般来说位运算的题就两种套路: 推式子, 按位考虑.

考虑每一位的贡献: 这一位上 $0$ 的个数乘 $1$ 的个数.

统计第 $i$ 位上 $1$ 的个数 $f_i$, 可以算出 $0$ 的个数为 $n - f_i$, 乘以 $2^{i - 1}$ 即为在十进制下的贡献.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const LL mod = 1e9 + 7;

LL f[70];
LL n, ans, a, x = 1;

int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a);
int j = 1;
while (a) {
f[j++] += a & 1LL;
a >>= 1LL;
}
}
for (int i = 1; i <= 60; ++i) {
ans = (ans + f[i] % mod * (n - f[i]) % mod * x % mod) % mod;
x = (x << 1LL) % mod;
}
printf("%lld\n", ans % mod);
return 0;
}