> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/bit-manipulation/xor/1442.-count-triplets-that-can-form-two-arrays-of-equal-xor.md).

# 1442. Count Triplets That Can Form Two Arrays of Equal XOR

https\://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

Given an array of integers `arr`.

We want to select three indices `i`, `j` and `k` where `(0 <= i < j <= k < arr.length)`.

Let's define `a` and `b` as follows:

* `a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]`
* `b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]`

Note that **^** denotes the **bitwise-xor** operation.

Return *the number of triplets* (`i`, `j` and `k`) Where `a == b`.

**Example 1:**

```
Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)
```

**Example 2:**

```
Input: arr = [1,1,1,1,1]
Output: 10
```

**Example 3:**

```
Input: arr = [2,3]
Output: 0
```

**Example 4:**

```
Input: arr = [1,3,5,7,9]
Output: 3
```

**Example 5:**

```
Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8
```

**Constraints:**

* `1 <= arr.length <= 300`
* `1 <= arr[i] <= 10^8`

对给定数组arr问三元组(i, j, k)满足xor(arr\[i:j]) == xor(arr\[j:k))的三元组个数。xor(arr\[i:j]) == xor(arr\[j:k))意味着xor(arr\[i:j]) ^ xor(arr\[j:k)) == xor(arr\[i:j]) == 0，此时对k，遍历i，当prexor\[i-1] ^ prexor\[k] == 0时，意味着对i，k，能和中间的所有j组成满足条件的三元组，res += k - i，总时间复杂度O(N^2)；进一步因为prexor\[i-1] ^ prexor\[k] == 0时，prexor\[i - 1] == prexor\[k]，所以可以统计每次prexor\[k]出现的频率和sum(出现的index)，也就是i-1的位置和，res += k - i for all i => res += freq(prexor\[k]) \* (k - 1) - (sum(i - 1) for all i that prexor\[i - 1] == prexor\[k])，初始时还有值0对应的位置-1和频率1，总时间复杂度O(N)。

```python
class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prexor, cur, res = {0: [1, -1]}, 0, 0
        for k, v in enumerate(arr):
            cur ^= v
            if cur not in prexor:
                prexor[cur] = [0, 0]
            f, t = prexor[cur]
            res += (k - 1) * f - t
            prexor[cur] = [f + 1, t + k]
        return res
                
```