โปรแกรมนับคู่ที่มี XOR อยู่ในช่วงใน Python

ปัญหา

กำหนดอาร์เรย์ nums และค่า l, r หาจำนวน Nice Pairs (i, j) ที่ i < j และ l ≤ (nums[i] XOR nums[j]) ≤ r

ตัวอย่าง

nums = [4,1,7,2], l = 2, r = 6 → Output: 6

Pairs: (1,0)=5, (1,2)=6, (1,3)=3, (0,3)=6, (0,2)=3, (2,3)=5

อัลกอริทึม (Bitwise Trie / DP on Bits)

นับคู่ที่ XOR ≤ X โดยใช้ Frequency Count และ Bit DP:

1. Count Frequency ของแต่ละค่าใน nums
2. Process ทีละบิตจาก LSB ไป MSB
3. ถ้า Bit ของ X เป็น 1: เพิ่มคู่ที่ XOR บิตนี้ = 0 (เหลือบิตต่ำกว่า ≤ X ที่เหลือ)
4. Merge Frequency: รวมค่าที่ต่างกันแค่บิตปัจจุบัน (Divide by 2)
5. Answer = Count(XOR ≤ r) - Count(XOR ≤ l-1)

ตัวอย่างโค้ด

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

ความซับซ้อน

• Time: O((n + U) log U) โดย U = ค่าสูงสุดใน nums
• Space: O(U)