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