Hiểu bài toán

Cho mảng A gồm N số nguyên. Đếm số cặp chỉ số (l, r) thỏa mãn:

1. Độ dài đoạn con [l, r] là số chẵn (r - l + 1 là chẵn).
2. XOR của nửa đầu bằng XOR của nửa sau.

Gọi mid = (l + r - 1)/2. Điều kiện 2 có thể viết là: A[l] ^ ... ^ A[mid] = A[mid+1] ^ ... ^ A[r].

Dựa trên tính chất của XOR (x ^ x = 0), ta có thể biến đổi: (A[l] ^ ... ^ A[mid]) ^ (A[mid+1] ^ ... ^ A[r]) = 0 => XOR của toàn bộ đoạn [l, r] bằng 0.

Đặt P[i] là XOR tiền tố (P[0] = 0, P[i] = A[1] ^ ... ^ A[i]). Khi đó XOR đoạn [l, r] là P[r] ^ P[l-1]. Điều kiện trở thành P[r] ^ P[l-1] = 0 => P[r] = P[l-1].

Ngoài ra, độ dài đoạn (r - l + 1) là chẵn. Rút gọn: Ta cần đếm số cặp chỉ số (i, j) với i < j, P[i] = P[j] và (j - i) là số chẵn.

Các cách tiếp cận

Cách Hash Map (Prefix XOR)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> a(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];

    vector<int> px(N + 1, 0);
    for (int i = 1; i <= N; ++i) px[i] = px[i-1] ^ a[i];

    unordered_map<int, long long> cnt_even, cnt_odd;
    cnt_even[0] = 1; // px[0] = 0 at index 0 (even)

    long long ans = 0;
    for (int r = 1; r <= N; ++r) {
        if (r % 2 == 0) {
            // r is even, need previous index i with same XOR and i even
            ans += cnt_even[px[r]];
            cnt_even[px[r]]++;
        } else {
            // r is odd, need previous index i with same XOR and i odd
            ans += cnt_odd[px[r]];
            cnt_odd[px[r]]++;
        }
    }

    cout << ans << '\n';
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này sử dụng kỹ thuật XOR tiền tố và hash map.

1. Tính mảng XOR tiền tố P, với P[i] = XOR của A[1...i].
2. Bài toán quy về tìm cặp (i, j) sao cho P[i] = P[j] và j - i là số chẵn.
   • j - i chẵn nghĩa là i và j cùng chẵn hoặc cùng lẻ.
3. Duyệt j từ 1 đến N:
   • Nếu j là số chẵn, ta cần đếm số i < j sao cho P[i] = P[j] và i chẵn.
   • Nếu j là số lẻ, ta cần đếm số i < j sao cho P[i] = P[j] và i lẻ.
4. Dùng hai hash map cnt_even và cnt_odd để lưu tần suất các giá trị P[i] cho các chỉ số i chẵn và lẻ tương ứng.
5. Khởi tạo cnt_even[0] = 1 (tương ứng với i=0).
6. Tại mỗi bước j, cộng dồn kết quả từ map tương ứng rồi cập nhật map.

Cách Hash Map (Batch Processing)

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

vector<long long> a(300001, 0);
unordered_map<int, int> frequent_even;
unordered_map<int, int> frequent_odd;

int main() {
    frequent_even[0] = 1;
    long long n, pre = 0, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre = (pre ^ a[i]);
        if (i % 2 == 0)
            frequent_even[pre]++;
        else
            frequent_odd[pre]++;
    }
    for (auto &i : frequent_even) {
        res += (long long)i.second * (i.second - 1) / 2;
    }
    for (auto &i : frequent_odd) {
        res += (long long)i.second * (i.second - 1) / 2;
    }
    cout << res;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này cũng dựa trên XOR tiền tố và chia nhóm theo độ chẵn/lẻ của chỉ số.

1. Tính XOR tiền tố P[i] cho tất cả i từ 0 đến N.
2. Phân loại các chỉ số i vào hai nhóm: chỉ số chẵn và chỉ số lẻ.
3. Với mỗi nhóm, ta cần đếm số cặp chỉ số (i, j) có cùng giá trị P.
   • Nếu có k chỉ số trong một nhóm có cùng giá trị P, số cặp tạo thành là k*(k-1)/2.
4. Duyệt một lần để điền vào hai hash map frequent_even và frequent_odd.
5. Sau đó, tính toán kết quả cho từng map.

So sánh với cách 1:

• Cách 1 (Online): Tính kết quả ngay trong khi duyệt (phù hợp nếu chỉ cần in ra).
• Cách 2 (Offline): Lưu trữ đầy đủ trước khi tính (dễ hiểu logic hơn).
• Về độ phức tạp và hiệu năng: Cả hai đều O(N). Cách 1 thường nhanh hơn một chút vì không cần duyệt map cuối cùng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Biến đổi điều kiện 'XOR nửa đầu = XOR nửa sau' thành 'Tổng XOR cả đoạn bằng 0' bằng cách XOR cả hai nửa lại. P[r] ^ P[l-1] = 0.
• Điều kiện độ dài chẵn (r - l + 1 chẵn) tương đương với việc chỉ số bắt đầu (l-1) và kết thúc (r) cùng chẵn hoặc cùng lẻ.
• Sử dụng Hash Map để đếm tần suất các giá trị XOR tiền tố cho từng nhóm chỉ số chẵn/lẻ.

Lỗi thường gặp

• Quên khởi tạo ban đầu cho hash map với giá trị P[0] = 0 tại chỉ số 0. Vì chỉ số 0 là số chẵn, cần khởi tạo cnt_even[0] = 1.
• Sử dụng biến số để tính XOR tiền tố nhưng không xử lý đúng kiểu dữ liệu nếu số lớn (trong C++ int thường đủ do a_i < 2^20, nhưng dùng long long cho an toàn).
• Nhầm lẫn giữa chỉ số mảng (bắt đầu từ 1) và chỉ số tiền tố (bắt đầu từ 0).