Chương trình C++ đếm cặp (l,r) có XOR bằng tổng

Cho mảng A kích thước N. Đếm số cặp (l,r) sao cho A[l] XOR ... XOR A[r] = A[l] + ... + A[r].

Ví dụ

Với A=[2,5,4,6], đầu ra 5. Các cặp: (1,1),(2,2),(3,3),(4,4),(1,2).

Giải thuật

Tiền tính tổng tiền tố s[i] và XOR tiền tố sx[i]. Với mỗi l, nhị phân tìm r lớn nhất sao cho s[r]-s[l-1] == sx[r]^sx[l-1]. Điều kiện này đúng khi không có bit nào bị carry khi cộng (tức không có vị trí nào cả hai số đều có bit 1). Cộng r-l+1 vào kết quả.

Mã C++

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

int solve(vector<int> A) {
    int n = A.size();
    vector<int> a(n + 1), s(n + 1), sx(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = A[i - 1];
        s[i] = s[i - 1] + a[i];
        sx[i] = sx[i - 1] ^ a[i];
    }
    int res = 0;
    for (int l = 1; l <= n; l++) {
        int bg = l, en = n, r = l;
        while (bg <= en) {
            int mi = (bg + en) / 2;
            if (s[mi] - s[l - 1] == (sx[mi] ^ sx[l - 1])) {
                r = mi;
                bg = mi + 1;
            } else en = mi - 1;
        }
        res += (r - l + 1);
    }
    return res;
}

int main() {
    vector<int> A = { 2, 5, 4, 6 };
    cout << solve(A) << endl;
}

Đầu vào / Đầu ra

Input: { 2, 5, 4, 6 }
Output: 5