XOR を扱う問題では、各bit 毎に分けて考えることが有効である場合が多いです。

\(j=0,1,\ldots,27\) に対して、\(A_i\) の \(j\) bit 目が \(1\) ならば \(B_i = 1\) 、\(0\) ならば \(B_i=0\) として長さ \(N\) の数列 \(B\) を定義します。（ここで \(j\leq 27\) なのは \(\mathrm{MAX_A} = 10^8 < 2^{27}\) であるからです。）

各 \(j\) について、\(B\) に対して本問題を解き、答えに \(2^j\) を掛けたものの総和が \(A\) に対する答えとなります。

このようにすると、\(A\) は様々な値を取るのに対し、\(B\) は \(0\) または \(1\) しか取らないため、考えやすくなります。

次に、\(\sum_{i=1}^{N-1}\sum_{j=i+1}^N (B_i \oplus B_{i+1}\oplus \ldots \oplus B_j)\) という形では ある区間の総 XOR が必要とされていますが、これは区間の和を計算する時累積和を使うのと同様に、累積XORを用いることで高速に計算できます。

具体的には、\(C_0=0, C_i =B_1\oplus \ldots \oplus B_i\) として累積 XOR の配列 \(C\) を定めます。

このとき、\(B_i \oplus B_{i+1}\oplus \ldots \oplus B_j = C_{i-1} \oplus C_j\) という等式が分かります。このことを用いると、計算する対象を以下の形で書くことが出来ます。

\[ \sum_{i=1}^{N-1}\sum_{j=i+1}^N (C_{i-1} \oplus C_j) = \sum_{i=0}^{N-2}\sum_{j=i+2}^N (C_{i} \oplus C_j) \]

ここで \(j\) の添え字が \(i+2\) から始まっている点が厄介です。そのため、以下の方法で添え字が \(i+1\) から始まるように変形します。

\[ \sum_{i=0}^{N-2}\sum_{j=i+2}^N (C_{i} \oplus C_j) = \sum_{i=0}^{N-1}\sum_{j=i+1}^N (C_{i} \oplus C_j) -\sum_{i=0}^{N-1} (C_i\oplus C_{i+1}) =\sum_{i=0}^{N-1}\sum_{j=i+1}^N (C_{i} \oplus C_j) - \sum_{i=1}^{N} B_i\]

このとき、\(\sum_{i=0}^{N-1}\sum_{j=i+1}^N (C_{i} \oplus C_j)\) の部分は \(C\) で値が異なる組の個数と等しいです。これは、\(C\) に含まれる \(0\) の個数と \(C\) に含まれる \(1\) の個数の積で求まります。

よって、計算したい値は、\(B\) の総和と、累積 XOR により得られる配列の \(0,1\) の個数を使用することで簡単に求められます。以上より、この問題を \(\mathrm{O}(N\log {\mathrm{MAX_A}})\) 時間で解くことができました。