数组相邻子阵上的异或

Question

从数组中，我需要找到通过对相邻子数组进行异或运算得到的值，然后对由此获得的值进行异或运算。在

输入

一行包含作为数组元素的整数。在

例[1,2,3]

输出

在单独的行中打印每个测试用例对应的答案。在

到目前为止，我使用循环和递归方法构建了两个策略。 我的方法中没有一种在大的输入大小上有很好的性能。在

例如，1异或2异或3异或（1异或2）异或（2异或3）异或（1异或2异或3）=2

你能建立一个更好的算法吗？也许是动态规划方法？在

from functools import reduce

# Calculate the XOR
def XOR(L):
    return reduce(lambda x, y: x ^ y, L)

# Recursive approach
def allSubArraysXOR(L,L2=None):
    if L2==None:
        L2 = L[:-1]
    if L==[]:
        if L2==[]:
            return 0
        return allSubArraysXOR(L2,L2[:-1])
    return XOR(L) ^ allSubArraysXOR(L[1:],L2)

# Loop - yielding approach
def getAllWindows(L):
    for w in range(1, len(L)+1):
        for i in range(len(L)-w+1):
            yield XOR(L[i:i+w])

a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(allSubArraysXOR(a))
# print(XOR(getAllWindows(a)))

Answer 1

我们不需要枚举（2**n）子数组来解决这个问题。

XOR有一些有用的特性，我们可以利用这些特性在O（n）时间内解决这个问题。具体来说：

• 对于任何k：k XOR k == 0
• 对于任何k：k XOR 0 == k。在
• XOR is both commutative and associative。在

为了解决您的问题，我们首先需要计算每个元素在子数组中出现的次数。任何出现偶数次的元素都可以忽略。其余的需要一起xood（每个只需要一次）。在

让我们看看这是如何应用到您的示例中的：

1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = # open brackets
1 XOR 2 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 XOR 1 XOR 2 XOR 3 =       # reorder
1 XOR 1 XOR 1 XOR 2 XOR 2 XOR 2 XOR 2 XOR 3 XOR 3 XOR 3 =       # group
(1 XOR 1 XOR 1) XOR (2 XOR 2 XOR 2 XOR 2) XOR (3 XOR 3 XOR 3) = # remove pairs
1 XOR 0 XOR 3 =
1 XOR 3 =
2

以下是这个想法的O（n）实现：

^{pr2}$

子阵列的计数由

count = (i + 1) * (n - i)

观察到当前元素的左边有i + 1个元素，右边有n - i个元素（也包括自身）。将两者相乘，将得到从当前元素的左侧开始，到其右侧结束的子阵列数。在

我们现在将问题简化为寻找乘积为奇数的(i + 1)和{}对。请注意，获得奇数积的唯一方法是将两个本身是奇数的数相乘（这可以通过考虑两个被乘数的素数因式分解得到）。在

有两种情况需要考虑：

• 当n为偶数时，(i + 1)和{}中的一个总是偶数的。这意味着对于偶数长度的列表，算法始终返回零。在
• 当n为奇数时，(i + 1) * (n - i)对i = 0, 2, 4, ..., (n - 1)是奇数。在

这导致了以下简化解决方案：

def xor_em(lst):
  if len(lst) % 2 == 0:
    return 0
  else:
    return reduce(operator.xor, lst[::2])