两两安定之和
Sum Of Pairwise Anding
我们得到一个大小为 N 的数组，我们必须计算 Ai AND(&) Aj 对于所有对 (i, j) where i < j. array 的大小可以和 10^5[=18 一样大=]。那么 calculate.Better 比 O(n^2).
最好的方法是什么？
我们可以独立解决每个位的问题。
对于固定位b，我们称将此位设置为一个的元素数f(b)。
答案是sum for all b f(b) * (f(b) - 1) / 2 * 2 ^ b.
为什么是正确的？假设 b 是固定的。当且仅当这两个数字都将此位设置为 1 时，两个数字的 and 才将此位设置为 1。如果设置了该位的元素数量为 f(b)，则恰好有 f(b) * (f(b) - 1) / 2 对使得两个元素都设置了该位。现在我们可以找到所有 b.
的总和
我们得到一个大小为 N 的数组，我们必须计算 Ai AND(&) Aj 对于所有对 (i, j) where i < j. array 的大小可以和 10^5[=18 一样大=]。那么 calculate.Better 比 O(n^2).
最好的方法是什么？我们可以独立解决每个位的问题。
对于固定位
b，我们称将此位设置为一个的元素数f(b)。答案是
sum for all b f(b) * (f(b) - 1) / 2 * 2 ^ b.
为什么是正确的？假设 b 是固定的。当且仅当这两个数字都将此位设置为 1 时，两个数字的 and 才将此位设置为 1。如果设置了该位的元素数量为 f(b)，则恰好有 f(b) * (f(b) - 1) / 2 对使得两个元素都设置了该位。现在我们可以找到所有 b.