题目大意
题目传送门
给定一个序列 \(a\)，问有多少个区间的异或和的二进制表示下一的个数为奇数。
思路
定义 \(f(l, r)\) 为区间 \([l, r]\) 之间的异或和，\(g(a)\) 表示 \(a\) 在二进制表示下 \(1\) 的个数。
因为 \(a \oplus a = 0\)，所以可以利用类似前缀和的数组 \(s_i\) 表示前 \(i\) 个数的异或和。则 \(f(l, r)\) 就等于 \(s_r \oplus s_{l - 1}\)。
所以问题转换为有多少个 \(l\) 和 \(r\)，使 \(g(s_r \oplus s_{l - 1}) \equiv 1 \ (mod \ 2)\) 为奇数，为了使式子更加简洁，不妨猜想 \(g(a \oplus b) \equiv (g(a) + g(b)) \ ( mod \ 2)\)。
可以知道，\(a\) 和 \(b\) 的二进制下如果在同一位最多出现一个 \(1\)，那么是没有问题的。如果当第 \(i\) 位 \(a\) 和 \(b\) 都是 \(1\)，\(1 + 1 - (1 \oplus 1) = 0\)，所以 \(g(a \oplus b) = g(a) + g(b) - 2 * g(a \& b)\)，因为 \(2\) 整除 \(2 * g(a \& b)\)，所以\(g(a \oplus b) \equiv (g(a) + g(b)) \ ( mod \ 2)\)。
所以问题进一步转化为求有多少组 \(l\)，\(r\)，使 \(g(l) + g(r) \equiv1 \ ( mod \ 2)\)。
所以要么 \(g(l) \equiv1 \ ( mod \ 2)\)，要么 \(g(r) \equiv1 \ ( mod \ 2)\)，所以，求出有多少个 \(s_i \equiv1 \ ( mod \ 2)\)，根据乘法原理就可以得出答案为 \(cnt_0 * cnt_1\)，要注意，当 \(i = 0\) 时的 \(s[i]\) 也要统计！！！
代码
#include <iostream>
using namespace std;const int N = 300010;
long long n, s, a, cnt;int main() {freopen("interval.in", "r", stdin);freopen("interval.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++) {cin >> a;s ^= a;if (__builtin_popcountll(s) % 2) cnt++;}cout << cnt * (n - cnt + 1) << endl;return 0;
}