E. Finding OR Sum 详细题解

一、关键数学恒等式

本题核心突破口是推导出：

$$(n \mid x) + (n \mid y)$$

的位按位展开式。

对任意一位二进制位 $b$（$0$ 或 $1$），观察这一位在 $x,y,n$ 中的取值：

设：

• $n_b$：$n$ 的第 $b$ 位
• $x_b$：$x$ 的第 $b$ 位
• $y_b$：$y$ 的第 $b$ 位

则该位对总和的贡献为：

$$(n_b \mid x_b) \cdot 2^b + (n_b \mid y_b) \cdot 2^b $$

按 $n_b=0/1$ 分类：

1）当 $n_b=0$ 时

贡献为：

$$(x_b + y_b)\cdot 2^b$$

2）当 $n_b=1$ 时

贡献恒为：

$$(1 + 1)\cdot 2^b = 2\cdot 2^b$$

整体表达式

令：

• $S = x + y$（所有位 $x_b+y_b$ 的加权和）
• $U = x \mid y$

则可以得到全局恒等式：

$$\boxed{(n \mid x)+(n \mid y) = S + \sum_{b:\,n_b=1,\,(x|y)_b=0} 2^b} $$

更简洁的最终形式：

$$\boxed{(n \mid x)+(n \mid y) = (x + y) + (n \,\&\, \sim\!(x \mid y))} $$

---

二、变量定义

我们只需要求出两个值：

1. $A = x + y$
2. $B = x \mid y$

一旦知道 $A,B$，对任意 $m$ 都可以 $O(1)$ 算出答案：

$$ans = A + (m \,\&\, \sim\! B)$$

---

三、询问策略（最多 2 次）

方案：用 $n=0$ 和 $n=2^{30}-1$

1. 询问 $n=0$

$$q_0 = (0|x)+(0|y) = x + y = A$$

直接得到 $A$。

2. 询问 $n = \text{ALL\_ONE} = 2^{30}-1$

$$q_{\text{all}} = (\text{ALL}|x)+(\text{ALL}|y) = \text{ALL} + \text{ALL} = 2(2^{30}-1) $$

这个询问其实可以不用，因为我们只需要 $A$ 和 $B$，而：

• 用 $n=0$ 得到 $A$
• 再随便问一个 $n\neq 0$ 即可解出 $B$

最简合法策略（只用 1 次或 2 次）

• 第 1 次问 $n=0$，得到 $A = x+y$。
• 第 2 次问任意 $n$（比如 $n=1$），得到：

$$q_1 = A + (1 \,\&\, \sim\! B)$$

移项得：

$$1 \,\&\, \sim\! B = q_1 - A$$

从而可以逐位恢复出 $B = x\mid y$。

实际最优解法： 只需要询问 $n=0$ 一次，就足够推出所有需要信息，满足 $\le 2$ 次限制。

---

四、最终答案公式

拿到 $A=x+y$ 和 $B=x|y$ 后，对给定的 $m$：

$$\boxed{ (m \mid x)+(m \mid y) = A + (m \,\&\, \sim\! B) } $$

---

五、算法流程

1. 询问 $n=0$，得到 $A = x + y$。 2.（可选）再询问一次任意 $n$，解出 $B = x \mid y$。
2. 输出 !。
3. 读入 $m$。
4. 用公式计算答案并输出。

---

六、复杂度

• 时间：$O(30)$ 每位处理
• 询问数：$\le 2$，完全满足题目限制

---

七、一句话总结

• $(n\mid x)+(n\mid y)$ 只和 $x+y$ 以及 $x\mid y$ 有关。
• 问 $n=0$ 直接得到 $x+y$。
• 再问一次即可推出 $x\mid y$。
• 之后任意 $m$ 都可以 $O(1)$ 计算。