题解 CF2180E No Effect XOR

JuRuoOIer · 2025-12-28 15:00:54 · 题解

题解 CF2180E No Effect XOR

其他题

题意

给定 l,r，求使得 \forall i\in[l,r],i\oplus x\in[l,r] 的正整数 x 的个数。

数据范围：多测，t\le 10^5,l,r\le 10^{15}。

做法

题解不太像人。这里讲讲按位考虑的做法。（upd：题解更按位考虑版了，虽然我没看。）

首先显然在 l\oplus r 最高位以上的部分是不贡献的，因为 [l,r] 内所有数在这些位上都只有一种取值，即 x 的这些位上只能填入 0。

然后我们假设 l\oplus r 的最高位为 k，则我们考虑第 k 位放 0 还是放 1。

• 如果放 0 的话，则第 k 位不变，此时要求 [l,2^k) 和 [2^k,r] 分别是封闭的。
  • 对于 [2^k,r]，我们同时减掉 2^k 就得到 [0,r-2^k]，明显只有 r-2^k 中末尾连续的 1 是符合题意的，其他部分一旦异或 1 均会跑到区间外面去。
  • 对于 [l,2^k)，根据异或的逆运算也是异或，我们发现异或 x 前后的数是一一对应的。所以 [l,2^k) 内封闭就等价于 [0,l) 内封闭。然后求法就同上。
• 如果放 1 的话，则第 k 位反转，此时要求两边能对应起来，根据我们刚才得到的一一对应原则，我们只能将 [l,r] 等分。设长度为 len，那么寻找 y<2^k 使得左部分的低 k 位，映射到右部分的低 k 位。左部分范围：[2^k-len,2^k-1]；右部分范围：[0,len-1]。所以我们需要 [2^k-len,2^k-1]\oplus y=[0,len-1]。注意到 [2^k-len,2^k-1]=[0,len-1]\oplus(2^k-1)，那么令 z=y\oplus(2^k-1)，则原式即为 [0,len-1]\oplus z=[0,len-1]，又回到第一种情况，计算就行。

两种情况相加减一（x 不能取 0）即可。复杂度单组 O(\log V)。