[ARC127D] Sum of Min of Xor 题解

先把 \(i\) 对 \(j\) 的约束去掉。没有 \(\min\) 的情况是 trival 的，发现瓶颈在于如何比较两个数之间的大小。

可以发现，对两个二进制数，我们本质上是想要找到它们第一个不同的位置。于是考虑从最高位开始，将 \((a_i,b_i)\) 按最高位分组为 \((0,0),(0,1),(1,0),(1,1)\) 四组。每组内部需要继续枚举低位，因此只考虑两组之间的贡献。

可以发现，有贡献的组对如下：

• \((0,0),(0,1)\)：此时贡献为 \(a_i\oplus a_j\)。
• \((0,0),(1,0)\)：此时贡献为 \(b_i\oplus b_j\)。
• \((1,1),(0,1)\)：此时贡献为 \(b_i\oplus b_j\)。
• \((1,1),(1,0)\)：此时贡献为 \(a_i\oplus a_j\)。
• \((0,0),(1,1)\)：贡献不确定，需要继续枚举，因此我们需要将这两组并在一起向下处理。
• \((0,1),(1,0)\)：贡献不确定，需要继续枚举，因此我们需要将这两组并在一起向下处理。

直接爆算即可。