异或平方和
题面
定义 $b_{i,j}$ 为 $a_i$ 的二进制的第 $j$ 位的值 . $f_{i,j,k}$ 为 $a_i \oplus a_j$ 的第 $k$ 位的值 .
$$ans = \sum_{i = 1} ^ n \sum_{j = 1} ^ n(a_i \oplus a_j) ^ 2$$
$$= \sum_{i = 1} ^ n \sum_{j = 1} ^ n(\sum_{k = 1} ^ {L}(b_{i,k} \oplus b_{j,k})2 ^ k) ^ 2$$
$$= \sum_{i = 1} ^ n\sum_{j = 1} ^ n\sum_{k = 1} ^ L \sum_{l = 1}^L f_{i,j,k}f_{i,j,l}2 ^ {k + l}$$
$$= \sum_{k = 1}^{L} \sum_{l = 1}^L 2^{k + l} (\sum_{i = 1}^n \sum_{j = 1}^n[f_{i,j,k} = 1 \And f_{i,j,l} = 1])$$
设 $dp_{i,j,0 / 1,0 / 1}$ 表示第 $i$ 位和第 $j$ 位的数的数量 .
复杂度 $O(n \log^2 \lvert V \rvert)$ .