C++で配列のすべての部分配列のXORの合計を求める方法

この問題では、n個の整数からなる配列 arr[] が与えられます。私たちの課題は、その配列のすべての部分配列（サブ配列）のXOR値の合計を求めるプログラムを作成することです。

具体的には、まず与えられた配列のすべての部分配列を列挙し、それぞれの部分配列について要素全体のXORを計算し、その値を合計用の変数に加算していきます。

問題例で理解しよう

入力: arr[] = {5, 1, 4}
出力: 19
説明: この配列のすべての部分配列のXORは次のようになります。
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5, 1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
合計 = 5 + 1 + 4 + 4 + 5 + 0 = 19

単純な解法：すべての部分配列を列挙する

もっとも直感的な解法は、多重ループを使ってすべての部分配列を生成し、各部分配列の要素のXORを計算して合計に加算していく方法です。

しかしこの方法はループの入れ子が必要となり、計算量がO(n³)程度に達するため非常に非効率です。配列のサイズが大きくなると、現実的な時間内に処理を終えることができません。

効率的な解法：プレフィックス（累積XOR）配列の活用

この問題を効率的に解くには、プレフィックス配列（累積XOR配列）を利用するのが有効です。この配列には、配列の先頭からインデックスiまでの要素のXORを格納します。すなわち、

prefixarr[i] = arr[0] ^ arr[1] ^ … ^ arr[i]

このプレフィックス配列を使えば、インデックスiからjまでの範囲の要素のXORは、次の式で簡単に求められます。

XOR(i〜j) = prefixarr[j] ^ prefixarr[i−1]　（i ≥ 1 の場合）
XOR(0〜j) = prefixarr[j]　（i = 0 の場合）

この公式を応用することで、すべての部分配列のXORを効率よく計算できます。

実装例

以下は、このソリューションの動作を示すC++プログラムです。このコードでは、各ビット位置ごとに「そのビットが立っている要素が奇数個含まれる部分配列」の個数を数え、それに基づいてXORの合計を効率的に算出しています。

#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
    int sum = 0;
    int multiplier = 1;
    for (int i = 0; i < 30; i++) {
        int oddCount = 0;
        bool isOdd = 0;
        for (int j = 0; j < n; j++) {
            if ((arr[j] & (1 << i)) > 0)
                isOdd = (!isOdd);
            if (isOdd)
                oddCount++;
        }
        for (int j = 0; j < n; j++) {
            sum += (multiplier * oddCount);
            if ((arr[j] & (1 << i)) > 0)
                oddCount = (n - j - oddCount);
        }
        multiplier *= 2;
    }
    return sum;
}
int main() {
    int arr[] = { 3, 8, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Sum of XOR of all subarrays is "<<calcSubArrayXORSum(arr, n);
    return 0;
}

出力

Sum of XOR of all subarrays is 46

実行結果より、配列 {3, 8, 13} のすべての部分配列のXORの合計が46であることが確認できます。