自动搬运

查看原文

来自洛谷，原作者为

	User_Unauthorized AFO

搬运于2025-08-24 22:54:51，当前版本为作者最后更新于2023-12-26 16:46:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

可以发现，$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)$ 的时间内回答每组询问。