Cho mảng nums và hai giá trị l, r. Tìm số cặp "đẹp" (i,j) với 0 ≤ i < j < n và l ≤ (nums[i] XOR nums[j]) ≤ r.
Ví dụ: nums = [4,1,7,2], l = 2, r = 6 → output = 6.
Giải thuật (Bitwise Trie / DP trên bit)
Hàm test(nums, x) đếm số cặp có XOR < x. Kết quả = test(r+1) - test(l).
- Dùng Counter đếm tần suất giá trị.
- Xử lý từng bit từ LSB đến MSB: nếu bit của x = 1, cộng cặp có XOR prefix = (x-1) tại bit hiện tại.
- Gom nhóm giá trị theo bit cao hơn (a >> 1) và lặp.
Code Python
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, r = 2, 6
print(solve(nums, l, r)) # 6
Đầu vào / Đầu ra
Input: [4,1,7,2], 2, 6
Output: 6