https://atcoder.jp/contests/abc147/tasks/abc147_d
もちろん素朴に計算していては間に合わないが、ビット毎に考えれば良い。
\(z_i = 1 \ll i\) とおくと、任意の \(x\) に対して \(x = \sum_i x \& z_i\) であり、 \((x \oplus y) \& z_i = (x \& z_i )\oplus (y \& z_i)\) である。
\(\sum_{i=1}^{N-1} \sum_{j=i+1}^N (A_i \oplus A_j) = \sum_k \sum_{i=1}^{N-1} \sum_{j=i+1}^N ((A_i \& z_k) \oplus (A_j \& z_k))\) であり、右のように変形すると、\(A_i \& z_k = 0\) または \(z_k\) であるので計算が簡単にできる。
\(B_k = \#\{ i \mid A_i \& z_k = 0 \}, C_k = \#\{ i \mid A_i \& z_k = z_k \}\) とおくと、 \((A_i \& z_k) \oplus (A_j \& z_k)\) は
- \(0 \oplus 0 = 0\)
- \(0 \oplus z_k = z_k\)
- \(z_k \oplus 0 = z_k\)
- \(z_k \oplus z_k = 0\)
の4通りなので、 \(\sum_{i=1}^{N-1} \sum_{j=i+1}^N ((A_i \& z_k) \oplus (A_j \& z_k)) = B_k * C_k * z_k\) である。 あとはこれを \(k\) について足し合わせる。