思想
异或结果与加法结果相同,说明两个数的二进制没有重复的1(不存在数位i,使得a[i]=b[i]=1)。因此,如果一段区间的数的异或结果相等,其子区间的异或结果也相等。因此,我们可以用双指针来看这样的区间有多少个。
代码
import java.io.*;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int[] a = new int[200010];
public static void main(String[] args)throws IOException{
int n = nextInt();
for(int i=0; i<n; i++) a[i] = nextInt();
int l=0, r=0, res=0;
long ans = 0;
while(l<n){
while(r<n && (res^a[r]) == (res+a[r])){
res ^= a[r];
r++;
}
ans += (r-l);
res ^= a[l];
l++;
}
out.println(ans);
out.flush();
out.close();
}
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
}