数列の任意の2つの項のXORの結果の合計を計算する方法

とある長さ $N$ の数列 $A_1, A_2, \dots , A_N$ に対し、 $1\leq i\leq j\leq N$ を満たす全ての組 $(i,j)$ について $A_i$ XOR $A_j$ をもとめ、その合計を計算する問題の解き方。

詳細については

Editorial - Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）

の後半に説明されている。

まず、ある桁数 $k$ に対し、すべての $1\leq i\leq N$ について、 $A_i$ の $k$ 桁目が1か0かを判定して、それぞれの $A_i$ の数を数える。例えば、 $k$ 桁目が1の数が $C_{k1}$ で、 $k$ 桁目が0の数が $C_{k0}$ の場合、 $k$ 桁目関して、合計の結果は $C_{k1} \times C_{k0} \times 2^{k-1}$ となる。

上記の計算を1桁目から $A_i$ の最大桁まで計算し、合計すれば、結果が求められる。