发表于 2024.08.22

• 不难得知，对于满足条件的三元组(i,j,k)，由于arr[i..j-1]的异或结果a等于arr[j..k]的异或结果a，那么a和b的异或结果为0，换句话说，子数组arr[i..k]所有的元素异或结果为0。反过来思考，如果某个长度为l的子数组中，所有元素异或的结果为0，那么该子数组中可以构造l - 1个满足条件的三元组。因此，题目转化为寻找所有元素异或结果为0的子数组，并计算其长度l，然后累加l - 1的和。

  怎么寻找这些子数组呢？我们可以使用一个数组prev_xor，其中prev_xor[i]表示第i个元素到当前元素的异或结果。那么可从左到右遍历数组arr，更新prev_xor，如果更新后某个prev_xor[i]的结果为0，那么从i到j的子数组满足条件，此时可以构造j - i个三元组。

  class Solution:
      def countTriplets(self, arr: List[int]) -> int:
          prev_xor = [0] * len(arr)
          ans = 0
          for i, num in enumerate(arr):
              for j in range(i - 1, -1, -1):
                  prev_xor[j] ^= num
                  if prev_xor[j] == 0:
                      ans += (i - j)
              prev_xor[i] = num
          return ans

• LC 题目链接