ABC147D
D - Xor Sum 4
https://gyazo.com/937c69af3cbbbb3b69f4e85db5d14453
考えたこと
二乗オーダーで計算してはいけない
行列全体のちょうど半分　行列の半分
XORと和の順序を交換できたりしないかな…
全桁の足し算にしちゃうと難しそうだけど、ビットごとならいけるのでは？
OK、0/1の列に対して下記が成り立つ
$ \sum_i^N x_i = K \iff \sum_i^N (1 \oplus x_i) = N - K XORと和の交換
つまり、あらかじめ全部の数の桁ごとの1の数を数えておき、Aiの1が立ってるところだけ上記の式で反転して和を求めればよい、桁数は60なので十分早い
ここで求めたものが行列全体なので、半分にすれば答え
公式解説
上記でも十分だが、公式解説では同様の変換をさらにやる
$ \sum_j \sum_i (x_i \oplus x_j) = \sum_j ([x_j = 0] K + [x_j = 1] (N - K)) = (N - K) K + K (N - K)
求める値はこの半分なので$ K (N - K)