Enumerate Xor Sum

桁ごとにその桁のbitが立つ方法の数を数えることができれば良いです。
$j$桁目（0-indexed）について考えます。
$A$の要素のうち$j$桁目のbitが立っているものの個数を$cnt_j$とします。
$k$個の要素を取り出すときに$j$桁目のbitが立つのは$A$の要素のうち$j$桁目のbitが立っているもののうち奇数個を取ったときに限ります。
それは$\sum_{i = 1}^{\lfloor\frac{k + 1}{2}\rfloor} \binom{cnt_j}{2i-1}\binom{N -cnt_j}{k-2i+1}\cdots(*)$ 通りです。
これを$k = 1,2,\cdots,N$について愚直に求めると全体で$Θ(N^2\log \max(A))$時間となり、実行時間制限に間に合いません。
$k = 1,2,\cdots,N$についてまとめて$(*)$を求めることを考えます。
そこで、長さがそれぞれ$cnt_j + 1,N -cnt_j+1$である0-indexedな数列$P_j,Q_j$を次のように定めます。
$P_j[i] = \binom{cnt_j}{i}(iが奇数の場合),0(iが偶数の場合)$
$Q_j[i] = \binom{N -cnt_j}{i}$
すると、$(*)$は$\sum_{i = 0}^{k} P_j[i]Q_j[k-i]$と書くことができます。これは畳み込みそのものです。
したがってこの問題を時間計算量$O(N\log N \log \max(A))$で解くことができました。