---
# System prepended metadata

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

---

# 1442. Count Triplets That Can Form Two Arrays of Equal XOR
# # Tóm tắt đề bài

Bạn được cho một mảng số nguyên `arr`.

Nhiệm vụ của bạn là tìm ba chỉ số `i, j,` và `k` sao cho:
- `0 ≤ i < j ≤ k < arr.length`

Định nghĩa hai giá trị a và b như sau:

* a là kết quả của phép XOR tất cả các phần tử từ chỉ số i đến j-1
* b là kết quả của phép XOR tất cả các phần tử từ chỉ số j đến k

Bạn cần đếm số bộ ba (i, j, k) thoả mãn điều kiện a = b.

### Giới hạn
* 1 <= arr.length <= 300
* 1 <= arr[i] <= 108

## Lời giải
- Với phép toán XOR, ta có nếu a = b thì **a^b = 0**.
- Vì vậy, nếu a ^ b ^ c ^ d = 0 thì ta có: a = b ^ c ^ d, a ^ b = c ^ d, a ^ b ^ c = d, b ^ d = a ^ c,....
- Giả sử nếu ta duyệt mảng và có **2, 5, 1** có XOR là 0 thì có bao nhiêu triplet có thể tạo ra từ tập đó?
- Trong trường hợp trên, (i, j, k) sẽ có vị trí như sau: i = 0, k = 2 (cố định) còn j sẽ có thể bằng 1 hoặc 2 (vì i < j <= k)
=> Có thể thấy, số triplet có thể tạo ra là **k - i**.
- Tóm lại, trong khoảng (i, k) ta tính được XOR của tất cả phần tử là 0 => ta chỉ cần tính số triplet tạo ra được trong khoảng (i, k) đó.

### Độ phức tạp thuật toán

Thời gian: $O(N^2)$
Bộ nhớ: $O(1)$ 

### Code tham khảo
```python
def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        res = 0
        for i in range(n - 1):
            cur_op = arr[i]
            for k in range(i + 1, n):
                cur_op ^= arr[k]
                if cur_op == 0:
                    res += (k - i)
        return res
```