<p><a href="https://atcoder.jp/contests/abc147/tasks/abc147_d">D - Xor Sum 4</a></p>
<ul>
<li><img src="https://gyazo.com/937c69af3cbbbb3b69f4e85db5d14453/thumb/1000" alt="image"></li>
<li>考えたこと<ul>
<li>二乗オーダーで計算してはいけない</li>
<li>行列全体のちょうど半分　<a href="/ja/%E8%A1%8C%E5%88%97%E3%81%AE%E5%8D%8A%E5%88%86">行列の半分</a></li>
<li>XORと和の順序を交換できたりしないかな…</li>
<li>全桁の足し算にしちゃうと難しそうだけど、ビットごとならいけるのでは？</li>
<li>OK、0/1の列に対して下記が成り立つ</li>
<li>$\sum_i^N x_i = K \iff \sum_i^N (1 \oplus x_i) = N - K$ <a href="/ja/XOR%E3%81%A8%E5%92%8C%E3%81%AE%E4%BA%A4%E6%8F%9B">XORと和の交換</a></li>
<li>つまり、あらかじめ全部の数の桁ごとの1の数を数えておき、Aiの1が立ってるところだけ上記の式で反転して和を求めればよい、桁数は60なので十分早い</li>
<li>ここで求めたものが行列全体なので、半分にすれば答え</li>
</ul>
</li>
<li>公式解説<ul>
<li>上記でも十分だが、公式解説では同様の変換をさらにやる</li>
<li>$\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)$</li>
<li>求める値はこの半分なので$K (N - K)$</li>
</ul>
</li>
</ul>


ABC147D