Đếm tập con có XOR bằng giá trị cho trước trong C++

Cho mảng arr[] và giá trị match. Đếm tập con có XOR các phần tử bằng match.

Động quy hoạch

• dp[i][j] = số tập con của arr[0..i-1] có XOR = j.
• Cơ sở: dp[0][0] = 1 (tập rỗng XOR = 0).
• Chuyển trạng thái: dp[i][j] = dp[i-1][j] + dp[i-1][j ^ arr[i-1]].
• Kết quả: dp[n][match].

Ví dụ hoàn chỉnh

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

int subset_XOR(int arr[], int size, int match) {
    int highest = arr[0];
    for (int i = 1; i < size; i++)
        if (arr[i] > highest)
            highest = arr[i];
    int temp = (1 << (int)(log2(highest) + 1)) - 1;
    if (match > temp)
        return 0;
    vector<vector<int>> dp(size + 1, vector<int>(temp + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= size; i++) {
        for (int j = 0; j <= temp; j++) {
            int temp_2 = dp[i - 1][j ^ arr[i - 1]];
            dp[i][j] = dp[i - 1][j] + temp_2;
        }
    }
    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 << "Số tập con XOR = " << match << ": " << subset_XOR(arr, size, match);
    return 0;
}

Kết quả

Số tập con XOR = 2: 8