C++で全ての部分配列のXORの総XORを効率的に求める方法

問題の概要

この問題では、n個の要素からなる配列が与えられます。求めるのは、その配列から作られるすべての可能な部分配列（連続する要素列）のXOR値をさらにXORで結合した結果を出力することです。

具体例を使って問題を確認してみましょう。

入力例

array = {1, 3, 6, 8}

出力例

0

計算内容

(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6) ^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)

つまり、長さ1の部分配列から配列全体まで、考えられるすべての部分配列についてXORを計算し、それらの結果をすべてXORで結びつけたものが答えとなります。

解法アプローチ

素朴な方法とその課題

最も単純な解法は、すべての部分配列を順に生成してそれぞれのXORを求め、それらをさらにXORで結合する方法です。しかし、この方法は部分配列の数がO(n²)個になるため、計算量が大きく非効率です。

XORの性質を利用した効率的な解法

より優れたアプローチは、各要素がすべての部分配列の中に何回現れるか（出現頻度）を数えるという発想です。ここで重要になるのがXORの次の性質です。

• 同じ値を偶数回XORすると結果は0になる
• 同じ値を奇数回XORするとその値自身が残る

この性質により、偶数回出現する要素は最終的な結果に影響しないため無視でき、奇数回出現する要素だけをXORすれば答えが得られることになります。

出現頻度を求める公式

インデックスi（0始まり）にある要素が、すべての部分配列の中で合計何回現れるかは、次の公式で一瞬にして計算できます。

出現頻度 = (i + 1) × (n - i)

これは、インデックスiの要素を含む部分配列の左端の選び方が(i+1)通り、右端の選び方が(n-i)通りあるためです。両者の積が、その要素を含む部分配列の総数、すなわち出現回数になります。

この公式で各要素の出現頻度を求め、頻度が奇数である要素のみをXORすれば、O(n)の計算量で最終結果を導き出せます。

C++での実装例

上記の解法を実装したプログラムが以下です。

#include <iostream>
using namespace std;

int xorSubarrayXors(int arr[], int N){
    int result = 0;
    for (int i = 0; i < N; i++){
        int frequency = (i + 1) * (N - i);
        if (frequency % 2 == 1)
            result ^= arr[i];
    }
    return result;
}

int main() {
    int arr[] = {1, 3, 6, 8};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The xor of all subarray xors is : " << xorSubarrayXors(arr, N);
    return 0;
}

実行結果

The xor of all subarray xors is : 0

まとめ

この問題は、XORの「偶数回の出現は打ち消される」という性質と、要素ごとの出現頻度を求める公式 (i+1)×(n-i) を組み合わせることで、部分配列を実際に列挙することなくO(n)の時間計算量で解くことができます。ブルートフォースなO(n³)やO(n²)の解法と比べ、大幅に効率的なアプローチと言えるでしょう。