使用 Python 编写程序，计算某个范围内的异或对

pythonserver side programmingprogramming更新于 2025/12/14 3:56:17

假设我们有一个数组 nums，其中有两个值 l 和 r，我们必须找出好对的数量。这里好对是一对 (i, j)，其中 0 <= i < j < nums 的大小和 l <= (nums[i] XOR nums[j]) <= r。

因此，如果输入为 nums = [4,1,7,2] l = 2 r = 6，则输出将为 6，因为合适的对为 (1,0): 1 XOR 4 = 5、(1,2): 1 XOR 7 = 6、(1,3): 1 XOR 2 = 3、(0,3): 4 XOR 2 = 6、(0,2): 4 XOR 7 = 3、 (2,3): 7 XOR 2 = 5。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 test() 。这将需要 nums、x
count := 包含 nums 中元素频率的映射
res := 0
当 x 非零时，执行
- 如果 x 为奇数，则
  - res := res + (count[a] * count[(x - 1) XOR a) 中所有元素的总和，对于 count 中的所有 a
- count := 具有键 a/2 和值的映射 (count[a] + count[a XOR 1]，对于 count 中的所有 a
- x = x/2 的商
返回 res / 的商2
从主方法返回 test(nums, r + 1) - test(nums, l)

示例

让我们看看下面的实现以便更好地理解

from collections import Counter
def solve(nums, l, r):
   def test(nums, x):
      count = Counter(nums)
      res = 0
      while x:
         if x & 1:
            res += sum(count[a] * count[(x - 1) ^ a] for a in count)
         count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
         x >>= 1
      return res // 2

   return test(nums, r + 1) - test(nums, l)

nums = [4,1,7,2]
l = 2
r = 6
print(solve(nums, l, r))