如何查找数组所有子数组的值的位xor
A = [1,2]
Output : 0
Explanation :
Sub Arrays :`[1], [2], [1,2]` (XOR of all subarrays = 0)
要回答这个问题，每个元素都必须决定它以奇数还是偶数为子阵列。奇怪的是，它将出现在XOR总和中，甚至不会出现。
位置i的元素将包含在(i+1) * (n-i)子阵列中。那是因为任何包含i的子阵列都以索引0、1，...，i开始。并以索引i，i 1，...，n-1结束。现在(i+1) * (n-1) = i(n-1) + i*i + n = (i+1)n (mod 2)，因为x^2 = x (mod 2)对于任何x。
因此，如果n甚至是奇数子阵列中都没有出现元素。如果n是奇数，则偶数索引的元素出现在奇数的子阵列中。
so：
def xor_all_subarrays(A):
if len(A) % 2 == 0:
return 0
r = 0
for i in xrange(0, len(A), 2):
r ^= A[i]
return r
如果使用子阵列您的意思是 PowerSets ，您可以使用以下事实：
- 对于大小的列表 n ，有2 n 列表，每个元素都在 2 2 n /2中出现em>;和
- 位XOR操作是交换性的，并且关联：
x ^ y ^ z等于z ^ x ^ y。
现在，如果列表大于一个元素，则每个元素都会发生： 2 n /2 times，这是两个的 pertair。如果您将元素两次XOR，则每个x的0：x ^ x = 0。因此，由于它是两个功率（大于或等于两个），因此每个元素的Xoring a a os a a power a tose a的功率将是0。如果有一个一个元素，则两个子阵列是[]和[x]，因此在这种情况下，结果为x。因此，快速算法是：
def xor_subarrays_powerset(data):
if len(data) == 1:
return data[0]
else:
return 0
在情况下，这些是连续性列表基于那里的索引，故事有些不同：
在此处元素 j （零索引）将在：
中n --- / min(j+1,n,i-n+1,n-j) --- i=1
的确，如果您有列表[1,2,3,4]：有以下" Windows"：
1,2,3,4
x
x
x
x
1 1 1 1
x x
x x
x x
1 2 2 1
x x x
x x x
1 2 2 1
x x x x
1 1 1 1
-------
4 6 6 4
，对于长度为5
的列表1,2,3,4,5
x
x
x
x
x
1 1 1 1 1
x x
x x
x x
x x
1 2 2 2 1
x x x
x x x
x x x
1 2 3 2 1
x x x x
x x x x
1 2 2 2 1
x x x x x
1 1 1 1 1
---------
5 8 9 8 5
所以我们注意到什么：
- 对于列表，第一个和最后一个元素始终被计数 n 次。这是合乎逻辑的，因为每个移动窗口只能通过这些元素一次。
- 第二个和一个但最后一个元素总是被计数 2＆Time;（N-2） 2 次。由于除了两次最小和最大的窗户以外的所有窗户;
- 第三个和两个但最后一个元素总是被计数 3＆times;（n-4） 2＆times; 2 2 times;
- 第四和三个但最后一个元素总是计数 4＆times;（n-6） 3＆times; 2 2＆times; 2 2 ;通常：
- i -th和 n-i - th元素（索引零， i＆leq; n/2 ）被计数（i） 1）和时代;（n-2＆times; i） ... 。 ... 并不重要，因为它们是两个的所有倍数。由于与自身的元素是
0，因此两个的倍数不计数。
因此，现在我们只需要确定元素是偶数贡献还是对总数奇怪。我们知道，如果列表的长度均匀， n 是均匀的，因此所有（n-2＆times; i），这意味着没有任何元素会贡献，结果为 0。如果列表为奇数，则第一个元素将贡献奇数（因为（i 1）＆times;（n-2＆times; i）是奇数），下一个元素甚至会做出贡献，下一个元素将再次贡献奇数。
因此，如果列表的长度有奇数，则意味着我们只需要XOR，而不是位于0，2，4的元素，...我们可以使用：
from itertools import islice
def xor_subarrays_contiguousness(data):
if len(data)&1:
r = 0
for e in islice(data,0,None,2):
r ^= e
return r
else:
return 0