偶数异或子数组的数量
用偶数异或找出子数组的数量（子数组的异或意味着其元素的异或）。例如：
l=[1,2,3,4] # ----> Answer of this is 4
（解释：[2],[4],[1,2,3],[1,2,3,4]--->这些是异或偶数的子数组，因此子数组数=4）
这是我的代码：
def odd_int(lst):
odd=0
for i in lst:
if i%2!=0:
odd+=1
return odd
l=list(map(int,input().split()))
x=0 # Denotes number of even xor arrays
for i in range(len(l)):
for j in range(i,len(l)):
l1=l[i:j+1]
y=odd_int(l1)
if y%2==0:
x+=1
print(x)
上面的代码超过了时间限制，所以有什么建议可以将它优化为 O(n)？？？谢谢你的时间！！！
回答
XOR 有一些很好的特性，允许使用额外空间的常量字进行线性时间解决方案。
第一个属性（形式上：可交换的、结合的，每个元素都是自逆的）提供了一种快速计算任意子数组 XOR 的方法。如果我们采用前缀 XORs
prefixXORs[0] = 0
prefixXORs[1] = prefixXORs[0] ^ l[0] = 1
prefixXORs[2] = prefixXORs[1] ^ l[1] = 3
prefixXORs[3] = prefixXORs[2] ^ l[2] = 0
prefixXORs[4] = prefixXORs[3] ^ l[3] = 4
然后我们可以计算
l[i] ^ ... ^ l[j] == prefixXORs[i] ^ prefixXORs[j + 1]
因此，问题变成了确定有多少对前缀异或具有偶数异或。
第二个属性是
even ^ even is even
even ^ odd is odd
odd ^ even is odd
odd ^ odd is even
因此，我们可以计算两者都是偶数或都是奇数的前缀异或对的数量。在 Python 中：
def count_even_subarrays(l):
prefixXOR = 0
evens = 1
odds = 0
for x in l:
prefixXOR ^= x
if prefixXOR % 2 == 0:
evens += 1
else:
odds += 1
return evens * (evens - 1) // 2 + odds * (odds - 1) // 2
print(count_even_subarrays([1, 2, 3, 4]))