思路与证明

关键变换

设 $x$ 的二进制在 $20$ 位内，令集合 $S$ 为 $x$ 中为 $1$ 的位位置集合，$C$ 为其补集（即 $x$ 中为 $0$ 的位，数量记为 $m$）。 对任意候选数 $a$，要让与任意另一个 $a'$ 有 $a$ & $a'$=$x$，显然 $a$ 在 $S$ 上必须全为 $1$。于是可以写成

其中 $b$ 只能在 $C$ 的这些位上取 $0/1$，在 $S$ 上必须为 $0$。

题目内容

小美有一个最喜欢的小于 $2^{20}$ 的非负整数 $x$ 。

我们称数组 $a$ 是 美丽的 ，当且仅当其满是以下所有条件：

• 数组 $a$ 中的每个元素都小于 $2^{20}$ 。