查找数组中的三元组 i、j、k 的数量，使得索引为 i 到 j-1 的元素的异或等于索引为 j 到 k 的元素的异或

Question

对于给定的正整数序列 A1,A2,…,AN，您应该找到满足 Ai^Ai+1^..^Aj-1 的三元组 (i,j,k) 的数量=Aj^Aj+1^..Ak 其中 ^ 表示按位异或。问题的 link 在这里：https://www.codechef.com/AUG19B/problems/KS1 我所做的就是尝试找到所有具有 xor 0 的子数组。该解决方案有效，但是是二次时间，因此太慢了。这是我设法找到的解决方案。

for (int i = 0; i < arr.length; i++) {
            int xor = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                xor ^= arr[j];
                if (xor == 0) {
                    ans += (j - i);
                }
            }
        }
        finAns.append(ans + "\n");

Answer 1

根据 CiaPan 在问题描述下的评论，O(n) 给出了解决方案：

If xor of items at indices I through J-1 equals that from J to K, then xor from I to K equals zero. And for any such subarray [I .. K] every J between I+1 and K-1 makes a triplet satisfying the requirements. And xor from I to K equals (xor from 0 to K) xor (xor from 0 to I-1). So I suppose you might find xor-s of all possible initial parts of the sequence and look for equal pairs of them.

函数f是主要方法。 brute_force 用于验证。

Python 2.7代码：

import random

def brute_force(A):
  res = 0

  for i in xrange(len(A) - 1):
    left = A[i]
    for j in xrange(i + 1, len(A)):
      if j > i + 1:
        left ^= A[j - 1]
      right = A[j]
      for k in xrange(j, len(A)):
        if k > j:
          right ^= A[k]
        if left == right:
          res += 1

  return res

def f(A):
  ps = [A[0]] + [0] * (len(A) - 1)
  for i in xrange(1, len(A)):
    ps[i] = ps[i- 1] ^ A[i]

  res = 0
  seen = {0: (-1, 1, 0)}

  for  i in xrange(len(A)):
    if ps[i] in seen:
      prev_i, i_count, count = seen[ps[i]]
      new_count = count + i_count * (i - prev_i) - 1
      res += new_count
      seen[ps[i]] = (i, i_count + 1, new_count)
    else:
      seen[ps[i]] = (i, 1, 0)

  return res

for i in xrange(100):
  A = [random.randint(1, 10) for x in xrange(200)]
  f_A, brute_force_A = f(A), brute_force(A)
  assert f_A == brute_force_A
print "Done"

查找数组中的三元组 i、j、k 的数量，使得索引为 i 到 j-1 的元素的异或等于索引为 j 到 k 的元素的异或

Find the number of triplets i,j,k in an array such that the xor of elements indexed i to j-1 is equal to the xor of elements indexed j to k

arrays

algorithm

math

xor

triplet