查找具有XOR和的数组的子数组数

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必须是偶数。所以只需使用前缀xor计数来计算偶数xor。需要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

Try it online!（带测试）

Answer 2

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

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

现在我们可以用偶数异或和来计算子数组。请注意，我们记得从零索引开始的子阵列已经有多少奇偶异或：

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