shakayamiさんのユーザ解説の発想と個人的に似ていると思います。

概要

binary trieを下のbitから考えるような方法で解くことができます。

\(A_i, A_j\) について、最下位bitが異なる場合、そのまま足すことができます。

最下位bitが両方0の場合、両方を2で割ってループさせます。

最下位bitが両方1の場合、両方2で割ったあと以下のようになります。

• \(A_i, A_j\) の最下位bitが異なるなら両方2で割る。同じになったら、足してさらに1を足したものが答え。

以上のようにして、\(A_i, A_j\) を足したあと2で割っていくのではなく、別々に値を持って考えることができます。これにより、以下のような主客転倒方針が可能になります。

答えを \(0\) で初期化し、\(i = j\) の場合を先に求めておきます。

その後、数列 \(A\) に対して手続き1を行います。

手続き1

数列 \(A\) を入力(引数)とします。

\(A\) のうち最下位bitが0になるものをまとめて数列 \(A_0'\) 、1になるものをまとめて数列 \(A_1'\) とします。

\(A_0'\) と \(A_1'\) の各組合せに対して和を求めてその総和を求めるのは容易なので、求めて答えに足します。

\(A_0', A_1'\) の中の要素をすべて2で割って切り捨てます。

\(A_0'\) が空でなければ \(A_0'\) に対して手続き1を繰り返し行います。

\(A_1'\) について手続き2を行います。

手続き2

数列 \(B\) を引数とします。

\(B\) のうち最下位bitが0になるものをまとめて数列 \(B_0'\) 、1になるものをまとめて数列 \(B_1'\) とします。

\(B_0'\) 内の2項の和は、手続き1で切り捨て除算したときの分の繰り上がりで最下位bitが1になります。なので、そのまま総和を求めることができるため、求めて答えに足し合わせます。

\(B_1'\) についても同様です。

\((B_0' , B_1)\) の 2項組について、手続き3を実行します。

手続き3

数列の組 \((C_0, C_1)\) を引数とします。\(C_0, C_1\) のどちらかが空なら手続き3を終了します。

\(C_0, C_1\) のすべての要素を2で切り捨て除算します。

\(C_0, C_1\) の要素を最下位bitで分け、\(C_{0, 0}, C_{0, 1}, C_{1, 0},C_{1, 1}\) とします。

\(C_{0, 0}, C_{1, 0}\) 内の要素の組み合わせは、下からの繰り上がりによって和の最下位bitが1になります。よって、その総和を求めるのは容易なので、求めて答えに足します。

\(C_{0, 1}, C_{1, 1}\) についても同様です。

\((C_{0, 0}, C_{1, 1})\) について手続き3を繰り返し行い、\((C_{0, 1}, C_{1, 0})\) について手続き3を繰り返し行います。

すべての手続きが終了したあとの答えを出力します。

計算量は \(O(N \log (\max(A)))\) です。

実装例 (C++, 100ms)

https://atcoder.jp/contests/abc384/submissions/60763883