นับ Subset ที่ XOR เท่ากับค่าที่กำหนด ใน C++

โจทย์: ให้อาร์เรย์ arr[] และค่า match ต้องการนับ Subset ที่ XOR ขององค์ประกอบเท่ากับ match

แนวคิด: Dynamic Programming

dp[i][j] = จำนวน subset จาก arr[0..i-1] ที่ XOR เท่ากับ j

Recurrence: dp[i][j] = dp[i-1][j] + dp[i-1][j ⊕ arr[i-1]]

ขอบเขตค่า XOR

ค่า XOR สูงสุด = (2^(⌊log₂(max)⌋+1)) - 1

โค้ด C++

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

int subset_XOR(int arr[], int size, int match) {
    int max_val = arr[0];
    for (int i = 1; i < size; i++)
        max_val = max(max_val, arr[i]);
    
    int max_xor = (1 << (int)(log2(max_val) + 1)) - 1;
    if (match > max_xor) return 0;
    
    vector<vector<int>> dp(size + 1, vector<int>(max_xor + 1, 0));
    dp[0][0] = 1;  // empty subset XOR = 0
    
    for (int i = 1; i <= size; i++) {
        for (int j = 0; j <= max_xor; j++) {
            dp[i][j] = dp[i-1][j];
            int xored = j ^ arr[i-1];
            if (xored <= max_xor)
                dp[i][j] += dp[i-1][xored];
        }
    }
    return dp[size][match];
}

int main() {
    int arr[] = {4, 2, 8, 10, 3, 4, 4};
    int match = 2;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "Count: " << subset_XOR(arr, size, match);
    return 0;
}

ผลลัพธ์

Count of number of subsets having a particular XOR value are: 8

ตัวอย่างตรวจสอบ

arr = {4, 2, 8, 10}, match = 12
Subsets: {4,8} (4⊕8=12), {4,2,10} (4⊕2⊕10=12) → 2 subsets

ความซับซ้อน: Time O(n × max_xor), Space O(n × max_xor)
สามารถลด Space เป็น O(max_xor) ได้ด้วย rolling array