โปรแกรม C++ นับคู่ l-r ที่ผล XOR เท่ากับผลรวม

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A N องค์ประกอบ ต้องการหาจำนวนคู่จำนวนเต็ม l และ r ที่ทำให้ A[l] XOR A[l+1] XOR ... XOR A[r] = A[l] + A[l+1] + ... + A[r]

ตัวอย่าง: A = [2, 5, 4, 6] ผลลัพธ์คือ 5 คู่ คือ (1,1), (2,2), (3,3), (4,4) และ (1,2)

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
กำหนดอาร์เรย์ a, s, sx ขนาด n+1
สำหรับ i := 1 ถึง n:
    a[i] := A[i-1]
    s[i] := s[i-1] + a[i]
    sx[i] := sx[i-1] XOR a[i]
res := 0
สำหรับ l := 1 ถึง n:
    bg := l, en = n, r = l
    while bg <= en:
        mi := (bg + en) / 2
        ถ้า s[mi] - s[l-1] == (sx[mi] XOR sx[l-1]):
            r := mi
            bg := mi + 1
        มิฉะนั้น:
            en := mi - 1
    res := res + (r - l + 1)
คืนค่า res

ตัวอย่างโค้ด 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;
}

อินพุต

{ 2, 5, 4, 6 }

เอาต์พุต

5