python - 偶数异或子数组的数量

Question

用偶数异或找出子数组的数量(子数组的异或意味着其元素的异或)。
例如:

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)？？？
谢谢你的时间!!!

Answer 1

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]))