haar_lib/typical/double_sigma/
xor.rs

1//! 2要素のXORの総和
2
3/// 2要素のXORの総和 $\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N a_i \oplus a_j$
4///
5/// **Time complexity** $O(64 * |a|)$
6///
7/// # Problems
8/// - <https://atcoder.jp/contests/abc147/tasks/abc147_d>
9pub fn sum_of_sum_of_xor(a: Vec<u64>) -> u128 {
10    let mut ret = 0;
11
12    for i in 0..64 {
13        let mut c = [0, 0];
14
15        for &x in &a {
16            if x & (1 << i) != 0 {
17                ret += c[0] << i;
18                c[1] += 1;
19            } else {
20                ret += c[1] << i;
21                c[0] += 1;
22            }
23        }
24    }
25
26    ret
27}