CPSCO2019 Session3 E - Enumerate Xor Sum

解法

$k$ のときの答えを求めてみます。
$X$ については、 $A_{i}$ の累積xorをとっておくことで $O(1)$ で求めることができるので割愛します。
$A_{i}$ と $X$ のxorを取った値を $Y$ とすると、xorの定義から、それぞれの桁について、 $A_{i},X$ の立ってるビットの個数が1ならば $Y$ のその桁は1、そうでなければ0となります。
$X$ について立っているビットは最初から決まっているので、 $A_{i}$ について、それぞれの桁で立っているビット、立っていないビットの個数が全部で何個あればいいか、というのがわかればよいことになります。
ということは、 $A_{1}$ から $A_{k}$ までのそれぞれのビットについて、立っている個数と立っていない個数を調べれば、 $X$ のビットによって場合分けをして、 $2^{p}$ を表すビットの部分は $A_{1} xor X +... + A_{k} xor X$ 全体で何回足されるか、というのが計算できるようになります。