haar_lib/typical/double_sigma/
range_xor.rs

1//! 区間XORの総和
2
3/// 区間XORの総和
4///
5/// Σ{i = 1 ~ N}Σ{j = i ~ N} aᵢ ⊕ aᵢ ₊ ₁ ⊕ ... ⊕ aⱼ
6///
7/// **Time complexity** $O(64 * |a|)$
8///
9/// # Problems
10/// - <https://atcoder.jp/contests/abc365/tasks/abc365_e>
11pub fn sum_of_sum_of_range_xor(a: Vec<u64>) -> u128 {
12    let mut ret = 0;
13
14    for b in 0..64 {
15        let mut count = [0, 0];
16        let mut sum = 0;
17
18        for &a in &a {
19            if a & (1 << b) == 0 {
20                count[0] += 1;
21            } else {
22                count.swap(0, 1);
23                count[1] += 1;
24            }
25
26            sum += count[1];
27        }
28
29        ret += sum << b;
30    }
31
32    ret
33}