Đếm bộ ba tạo thành hai mảng XOR bằng nhau (Count Triplets That Can Form Two Arrays of Equal XOR) trong C++

Cho mảng arr. Tìm số bộ ba chỉ số (i, j, k) với 0 ≤ i < j ≤ k < N sao cho XOR đoạn [i, j-1] bằng XOR đoạn [j, k].

Ví dụ

Đầu vào: [2,3,1,6,7]
Đầu ra: 4 (các bộ ba: (0,1,2), (0,2,2), (2,3,4), (2,4,4)).

Quan sát quan trọng

XOR đoạn a = arr[i]⊕...⊕arr[j-1], b = arr[j]⊕...⊕arr[k]. Điều kiện a == b ⇔ a ⊕ b = 0 ⇔ XOR toàn bộ đoạn [i, k] = 0. Với mọi đoạn [i, k] có XOR = 0, có thể chọn j bất kỳ trong (i, k] → có k - i cách chọn.

Thuật toán tối ưu O(N^2)

1. Tính mảng prefix XOR: pref[0]=0, pref[i+1]=pref[i]⊕arr[i].
2. Đoạn [i, k] có XOR = 0 ⇔ pref[i] == pref[k+1].
3. Duyệt i từ 0 đến n-1, k từ i+1 đến n-1, nếu pref[i] == pref[k+1] thì ans += k - i.

Triển khai C++ (tối ưu hơn code gốc)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();
        vector pref(n+1);
        for (int i = 0; i < n; ++i) pref[i+1] = pref[i] ^ arr[i];
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int k = i+1; k < n; ++k)
                if (pref[i] == pref[k+1]) ans += k - i;
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N^2) - đủ nhanh cho N ≤ 300.
• Không gian: O(N) - mảng prefix XOR.

Kết quả kiểm thử

Đầu vào: {2,3,1,6,7}
Đầu ra: 4