And 题解

· · 题解

可以发现，x \operatorname{AND} y 对应了在二进制加法中进位的位置集合，x \operatorname{XOR} y 对应了结果中为 1 但是没有进位的位置集合。因此，通过用位运算模拟加法的过程，我们可以得出

x + y = 2 \times \left(x \operatorname{AND} y\right) + x \operatorname{XOR} y

因为已知 x + y 和 x \operatorname{AND} y，因此可以得到 x \operatorname{XOR} y，设为 C。

那么所有可能的合法数对可以通过将 C 二进制下的 1 分配给 x 或 y 得到。注意到若 C \operatorname{AND} B 不为 0 那么不存在合法的分配方案，此时应按无解处理。

通过一些观察可以发现 C 二进制下最高位的 1 一定分配给 y，否则无法保证 x \le y。在这之后的所有情况均合法，所以可以发现对于一种方案，将 C 二进制下除最高位的其他位分配方案取反，得到的方案也是合法的，且与原方案互补。

所以只会有 C 二进制下最高位的 1 产生贡献，贡献系数为剩余位数的方案数，即 2 ^{\operatorname{popcount}\left(C\right) - 1}。

因此我们可以在 \mathcal{O}\left(1\right) 的时间内回答每组询问。