用异或和求一个数组的子数组个数

Question

给定如下数组A，我们需要计算具有XOR和X的子数组的总数，子数组应满足条件(X+1) = (X^1)。这是我的解决方案，

def getTotalXorOfSubarrayXors(arr, N):
X = 0
count = 0
for i in range(0, N):
for j in range(i, N):
for k in range(i, j + 1):
X = X ^ arr[k]
if X+1 == X^1:
count +=1
X = 0
return count
arr = [3, 5, 2, 4, 6]
N = len(A)
print(getTotalXorOfSubarrayXors(A, N))

但是这个解的时间复杂度是O(n^3)，超过了我对大数组集的时间限制。是否有任何方法可以优化这段代码，以减少时间复杂度?

Answer 1

条件(X+1) = (X^1)仅表示X必须是偶数。所以只要用前缀计数来计算偶数。占用O(n)个时间和O(1)个空间

def getTotalXorOfSubarrayXors(A, _):
X = 0
counts = [1, 0]
total = 0
for a in A:
X ^= a & 1
total += counts[X]
counts[X] += 1
return total

上网试试!(测试)

Answer 2

操作X ^ 1修改数字的最后一位。因此，****1变成****0，反之亦然。

因此我们可以看到，对于X的奇数值，X ^ 1的值小于X，但对于X的偶数值，X ^ 1的值比X大1，这正是我们所需要的。

现在我们可以计数具有偶数或和的子数组了。注意，我们还记得从0索引

开始的子数组已经有多少奇和和和。

def Xors(arr, N):
oddcnt = 0
evencnt = 0
res = 0
x = 0
for p in arr:
x ^= p
if (x % 2):
res += oddcnt
oddcnt += 1
else:
evencnt += 1
res += evencnt
return res