C++で特定のXOR値を持つ部分集合の個数を数える方法

正の整数を含む配列 arr[] と整数値 match が与えられたとき、要素のXOR(排他的論理和)がちょうど match と一致する部分集合(サブセット)の個数を求めるのがこの問題の目的です。

例

入力1

arr[] = {4, 2, 8, 10}、match = 12

出力1

特定のXOR値を持つ部分集合の個数: 2

説明

XORが12になる部分集合は次の2つです。

[4, 8]、[4, 2, 10]

実際に、4 XOR 8 = 12、4 XOR 2 XOR 10 = 12 となり、どちらも条件を満たしています。

入力2

arr[] = {3, 5, 2, 7}、match = 5

出力2

特定のXOR値を持つ部分集合の個数: 2

説明

XORが5になる部分集合は次の2つです。

[5]、[2, 7]

要素5単体でも、2 XOR 7 = 5 でも条件を満たします。

プログラムで使用するアプローチ

ここでは動的計画法(DP)を用いて解きます。2次元配列 arr_2[][] を用意し、arr_2[i][j] には「arr[0]〜arr[i-1] の範囲から選んだ部分集合のうち、XOR値が j になるものの個数」を格納します。

空集合のXORは 0 であり、これを実現する部分集合は空集合自身の1つだけなので、初期値として arr_2[0][0] = 1 を設定します。

状態遷移は次の漸化式で表されます。

arr_2[i][j] = arr_2[i-1][j] + arr_2[i-1][j ^ arr[i-1]]

この式は次の2つの場合の組み合わせを意味しています。

• arr[i-1] を部分集合に含めない場合: arr[0〜i-2] の部分集合のXORが j であれば、arr[i-1] を加えなくてもXORは j のままです(arr_2[i-1][j] の分)。
• arr[i-1] を部分集合に含める場合: arr[0〜i-2] の部分集合のXORが j ^ arr[i-1] であれば、そこへ arr[i-1] を加えると (j ^ arr[i-1]) ^ arr[i-1] = j となり、XORが j になります(arr_2[i-1][j ^ arr[i-1]] の分)。

最終的な答えは arr_2[size][match] に格納されます。

アルゴリズムの手順

• 整数型配列 arr[] と整数変数 match を用意します。
• 関数 subset_XOR(int arr[], int size, int match) は、入力配列とその長さを受け取り、特定のXOR値を持つ部分集合の個数を返します。
• 最初に highest = arr[0] とし、forループで配列全体を走査して最大値を highest に求めます。
• 取り得る最大のXOR値として temp = (1 << (int)(log2(highest) + 1)) - 1 を計算します。
• XOR値を記録するための2次元配列 arr_2[size+1][temp+1] を宣言します。
• forループで arr_2 の全要素を 0 で初期化します。
• arr_2[0][0] = 1 を設定します。
• i = 1〜size、j = 0〜temp の二重ループで、temp_2 = arr_2[i-1][j ^ arr[i-1]] を求め、arr_2[i][j] = arr_2[i-1][j] + temp_2 を計算します。
• ループ完了後、arr_2[size][match] が求める個数になります。
• 結果として arr_2[size][match] を返します。

このアルゴリズムの時間計算量・空間計算量は、いずれも O(size × temp) です。

C++による実装例

#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;
    }
    int arr_2[size+1][temp+1];
    for (int i = 0; i <= size; i++){
        for (int j = 0; j <= temp; j++){
            arr_2[i][j] = 0;
        }
    }
    arr_2[0][0] = 1;
    for (int i = 1; i <= size; i++){
        for (int j = 0; j <= temp; j++){
            int temp_2 = arr_2[i-1][j ^ arr[i-1]];
            arr_2[i][j] = arr_2[i-1][j] + temp_2;
        }
    }
    return arr_2[size][match];
}
int main(){
    int arr[] = {4, 2, 8, 10, 3, 4, 4};
    int match = 2;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "特定のXOR値を持つ部分集合の個数: " << subset_XOR(arr, size, match);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

特定のXOR値を持つ部分集合の個数: 8

なお、このコードでは配列サイズを実行時に決定する可変長配列(VLA)を使用しているため、GCCなどVLAをサポートするコンパイラが必要です。厳密なC++規格への準拠を重視する場合は、std::vector を利用するとよいでしょう。