和和异或和 题解

这题不是暴力吗（（（

注意到 $x\oplus y\le x+y$，且 $x\oplus y=x+y$ 当且仅当 $x,y$ 所有为 $1$ 的位都不同。

所以区间长度不超过 $\log_2 V$。

于是就可以暴力了。

#include <iostream>
#include <cstdio>
using namespace std;
int a[200005];
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	for(int i = 1; i <= 30; i++){
		for(int j = 1; j <= n - i + 1; j++){
			int cur1 = 0, cur2 = 0;
			for(int k = j; k <= j + i - 1; k++){
				cur1 += a[k];
				cur2 ^= a[k];
			}
			if(cur1 == cur2) ans++;
		}
	}
	cout << ans << '\n';

	return 0;
}

时间复杂度：$O(n\log^2 V)$。