题意
有一个长度为 \(n\) 的序列 \(a\),你需要求出:
\[\sum_{i = 1}^n \sum_{j = 1}^n (a_i \text{and} a_j)(a_i \text{or} a_j)(a_i \text{xor} a_j)
\]
solution
首先对于每个结果拆位,也就是对于原式中的三项,我们需要枚举三个位 \(i, j, k\),求有多少对数经过上述操作后对应的 \(i, j, k\) 位结果为 \(1\),可以简单的使用一个桶记入信息,可以做到 \(O(n \log^3 n)\)。
更为强势的做法是,考虑上述过程本质上是钦定一些位置为 \(0\),剩下随便选,可以用 FMT 做到 \(O(n \log n)\)。