haar_lib/typical/double_sigma/
range_xor.rs

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