AtCoder ABC 147 D - Xor Sum 4

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$ について足し合わせる。

https://atcoder.jp/contests/abc147/submissions/32456970