ABC147D

D - Xor Sum 4

• 
• 考えたこと
  • 二乗オーダーで計算してはいけない
  • 行列全体のちょうど半分　行列の半分
  • XORと和の順序を交換できたりしないかな…
  • 全桁の足し算にしちゃうと難しそうだけど、ビットごとならいけるのでは？
  • OK、0/1の列に対して下記が成り立つ
  • ${\sum }_i^N{x}_i=K⟺{\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)$