Tối đa hóa số mảng con có XOR = 0 trong C++

Cho mảng Arr[] số nguyên. Tìm số lượng mảng con tối đa có XOR = 0 sau khi hoán đổi bit tùy ý. Điều kiện:

• Số bit 1 (set bits) trong đoạn [L,R] là chẵn.
• Tổng bit trong đoạn ≤ 2 × (số bit 1 lớn nhất trong đoạn).

Ví dụ

Đầu vào: Arr[] = {1, 2, 5, 4}

Đầu ra: Chỉ điều kiện 1: 4 mảng con. Cả 2 điều kiện: 3 mảng con.

Đầu vào: Arr[] = {3, 7, 2, 9}

Đầu ra: Chỉ điều kiện 1: 6. Cả 2: 3.

Phương pháp giải

• Điều kiện 1 (XOR=0 ↔ số bit 1 chẵn): Dùng mảng prefix đếm số bit 1. Số cặp (i,j) có prefix cùng chẵn/lẻ = C(even,2)+C(odd,2).
• Điều kiện 2: Duyệt i, mở rộng j tối đa 60 phần tử (vì >60 thì tổng bit > 2*max). Đếm đoạn vi phạm điều kiện 2 (tổng chẵn nhưng 2*max > tổng).
• Kết quả = (số đoạn thỏa điều kiện 1) - (số đoạn vi phạm điều kiện 2).

Ví dụ mã C++

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

int removeSubarr(int arr[], int len) {
    int count = 0;
    for (int i = 0; i < len; i++) {
        int sum = 0, maxVal = 0;
        for (int j = i; j < min(len, i + 60); j++) {
            sum += arr[j];
            maxVal = max(maxVal, arr[j]);
            if (sum % 2 == 0 && 2 * maxVal > sum) count++;
        }
    }
    return count;
}

int findSubarrays(int arr1[], int len1) {
    int prefix[len1];
    for (int i = 0; i < len1; i++) arr1[i] = __builtin_popcountll(arr1[i]);
    for (int i = 0; i < len1; i++) {
        prefix[i] = arr1[i];
        if (i != 0) prefix[i] += prefix[i-1];
    }
    int odd = 0, even = 0;
    for (int i = 0; i < len1; i++) {
        if (prefix[i] % 2 == 0) even++; else odd++;
    }
    even++; // prefix[-1] = 0 (chẵn)
    long long tmp1 = 1LL * odd * (odd - 1) / 2;
    long long tmp2 = 1LL * even * (even - 1) / 2;
    long long result = tmp1 + tmp2;
    cout << "Subarrays satisfying only 1st condition: " << result << endl;
    result -= removeSubarr(arr1, len1);
    cout << "Subarrays satisfying both conditions: ";
    return result;
}

int main() {
    int Arr[] = {1, 2, 5, 4};
    int length = sizeof(Arr)/sizeof(Arr[0]);
    cout << findSubarrays(Arr, length);
    return 0;
}

Đầu ra chương trình

Subarrays satisfying only 1st condition: 4
Subarrays satisfying both condition: 3