โปรแกรมคำนวณ kpr sum สำหรับทุกคิวรีใน Python

มีอาร์เรย์ nums และคิวรี queries[i]=[k,p,r] คำนวณ:

kpr_sum = Σ_{i=P}^{R-1} Σ_{j=i+1}^{R} (K XOR (A[i] XOR A[j]))

มอดุลลอ 10^9+7

ตัวอย่าง: nums=[1,2,3], queries=[[1,1,3],[2,1,3]] ผลลัพธ์ [5,4]

วิธีแก้ปัญหา (Bitwise Prefix Sum)

1. คำนวณ prefix sum ของบิตแต่ละตำแหน่ง (0..19) ของ nums
2. แต่ละคิวรี: นับจำนวนบิต 1 (n1) และ 0 (n0) ในช่วง [P,R]
3. ถ้าบิตของ K เป็น 1: ใช้คู่ที่บิตเหมือนกัน (n1*(n1-1)+n0*(n0-1))/2
4. ถ้าบิตของ K เป็น 0: ใช้คู่ที่บิตต่างกัน n1*n0
5. รวมทุกบิต.shift ตามตำแหน่ง

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

def solve(nums, queries):
    m = 10**9 + 7
    N = len(nums)
    q_cnt = len(queries)
    C = []
    for i in range(20):
        R = [0]
        t = 0
        for x in nums:
            t += (x >> i) & 1
            R.append(t)
        C.append(R)
    res = []
    for j in range(q_cnt):
        K, P, R = queries[j]
        d = R - P + 1
        t = 0
        for i in range(20):
            n1 = C[i][R] - C[i][P-1]
            n0 = d - n1
            if (K >> i) & 1:
                x = (n1*(n1-1) + n0*(n0-1)) >> 1
            else:
                x = n1 * n0
            t = (t + (x << i)) % m
        res.append(t)
    return res

nums = [1,2,3]
queries = [[1,1,3],[2,1,3]]
print(solve(nums, queries))

อินพุต

[1,2,3], [[1,1,3],[2,1,3]]

เอาต์พุต

[5, 4]