解题思路
我们需要计算使安全强度 V=x⊕a⊕b 取得最大值的有序数对 (a,b) 的个数,其中 a∈[A,B],b∈[C,D],所有整数 <231。
因为异或运算按位独立,且高位权重大于低位,我们可以采用从高位到低位的贪心策略:
- 从最高可参与位(第 30 位)开始,逐位决定当前位是否能取 1。
- 若在当前位,存在某种合法的 a 和 b 的取值,使得 xi⊕ai⊕bi=1,则为了最大化最终结果,必须让这一位为 1,即只保留使当前位异或结果为 1 的转移。
- 若所有合法取值都只能使当前位异或结果为 0,则退而求其次,保留结果为 0 的转移。