本解説において、操作前の数列を \(A\)、操作後の数列を \(B\) と書くことにします。

[1] 操作後の数列の特徴付け

操作後の数列 \(B\) について、次が成り立ちます：

• 任意の \(i, j\) に対して、\(A_i\oplus A_j = B_i\oplus B_j\)。
• 操作回数が \(1\) 回以上であれば、\(B_i = 0\) となる \(i\) が存在する。

前者の性質は、任意の非負整数 \(a, b, x\) に対して \(a\oplus b = (a\oplus x) \oplus (b\oplus x)\) であることから分かります。後者の性質は、操作回数が \(1\) 回以上であるとき、最後に選んだ \(x\) と等しい 項が \(0\) に変化することから分かります。

このことから、操作後の数列 \(B\) は次の形のものに限られることが分かります。

• 操作前の数列 \(A\) と同一の数列（操作を一度も行わない場合）。
• ある \(k\) に対し、\(B_i = A_i\oplus A_k\) (\(1\leq i\leq N\)) により定まる数列。

逆に、これらの数列 \(B\) は操作後の数列として得ることが可能です（操作を \(0\) 回または \(1\) 回行うことを考えれば十分です）。

[2] 答の計算

操作後の数列 \(B\) としてありうるものが全て決定できました。これらすべてに対して \(\sum_{i=1}^N B_i\) を計算できれば、答を求めることができます。

したがって各 \(x\in \{0, A_1, \ldots, A_N\}\) に対して \(\sum_{i=1}^N (A_i\oplus x)\) が計算できればよいです。\(\max_i A_i < 2^K\) となる \(K\) をとり、この計算を

• 各 \(k (0\leq k < K)\) に対して、\((A_i\oplus x)\) の \(2^k\) の位の総和を求める。
• それらを合計する。

という手順で行うことを考えると、この計算は次の計算方法・計算量で行うことができます。

• 事前に、各 \(k\) に対して、\(A_i\) の \(2^k\) の位のうち \(0, 1\) であるものの個数を求めておく（\(\Theta(NK)\) 時間）。
• その結果を利用して、各 \(x\) に対して \(\sum_{i} (A_i\oplus x)\) を計算する（\(x\) ごとに \(\Theta(K)\) 時間、全体で \(\Theta(NK)\) 時間）。

以上をまとめて、本問は \(\Theta(NK)\) 時間で解くことができます。

• 解答例 (Python)：https://atcoder.jp/contests/arc135/submissions/29030561