เพิ่มจำนวนซับอาร์เรย์ที่ XOR เป็นศูนย์สูงสุดใน C++

ได้รับอาร์เรย์ Arr[] จำนวนเต็ม หาจำนวนซับอาร์เรย์สูงสุดที่ XOR เป็น 0 ได้ โดยสามารถสลับบิตของซับอาร์เรย์ได้ไม่จำกัดครั้ง (1 ≤ Arr[i] ≤ 10¹⁸)

เงื่อนไข 2 ข้อเพื่อให้ซับอาร์เรย์ XOR เป็น 0 โดยการสลับบิต:

• จำนวน set bits ในช่วง left ถึง right เป็นเลขคู่
• สำหรับช่วงใดๆ: ผลรวมบิต ≤ 2 × (ค่าสูงสุดของ set bits)

ตัวอย่าง

Input: Arr[] = {1, 2, 5, 4}

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

Input: Arr[] = {3, 7, 2, 9}

Output: Subarrays satisfying only 1st condition: 6
Subarrays satisfying both conditions: 3

อัลกอริทึม

• ฟังก์ชัน removeSubarr(arr, len) นับซับอาร์เรย์ที่ ไม่ ตรงเงื่อนไขข้อ 2
• วน i=0..len-1, ในแต่ละ i วน j=i..min(len, i+60) (เกิน 60 เงื่อนไข 2 จะไม่เป็นเท็จอีก) สะสม sum และ maxVal
• ถ้า sum คู่ และ 2×maxVal > sum → เพิ่ม count (ไม่ผ่านเงื่อนไข 2)
• ฟังก์ชัน findSubarrays(arr1, len1) นับซับอาร์เรย์ผ่านเงื่อนไข 1 (prefix sum parity) แล้วลบ count จาก removeSubarr
• ใช้ __builtin_popcountll นับ set bits แต่ละตัว
• Prefix array: prefix[i] = prefix[i-1] + popcount(arr1[i])
• นับค่า prefix คู่/คี่ → คำนวณจำนวนคู่ (nC2) รวมกันได้เงื่อนไข 1
• ลบ count ที่ไม่ผ่านเงื่อนไข 2 → ได้คำตอบสุดท้าย

ตัวอย่างโค้ด 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];
    int oddcount = 0, evencount = 0;
    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];
    }
    for (int i = 0; i < len1; i++) {
        if (prefix[i] % 2 == 0) evencount++;
        else oddcount++;
    }
    evencount++;
    int tmp1 = (oddcount * (oddcount - 1)) / 2;
    int tmp2 = (evencount * (evencount - 1)) / 2;
    int result = tmp1 + tmp2;
    cout << "Subarrays satisfying only 1st condition: " << result << endl;
    cout << "Subarrays satisfying both conditions: ";
    result -= removeSubarr(arr1, len1);
    return result;
}

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

ผลลัพธ์

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