Chương trình tìm tổng kpr cho tất cả các truy vấn cho một danh sách các số nhất định trong Python

Giả sử chúng ta có một danh sách các số nums. Chúng ta cũng có một danh sách các truy vấn trong đó các truy vấn [i] chứa ba phần tử [k, p, r], đối với mỗi truy vấn, chúng ta sẽ phải tìm kpr_sum. Công thức cho kpr_sum như dưới đây.

$$ \ mathrm {{𝑘𝑝𝑟} \ _ {𝑠𝑢𝑚} =\ sum _ {\ substack {𝑖 =𝑃}} ^ {𝑅 − 1} \ sum _ {\ substack {𝑗 =𝑖 + 1}} ^ {𝑅} (𝐾 ⊕ (𝐴 [𝑖] ⊕𝐴 [𝑗]))} $$

Nếu tổng quá lớn, hãy trả về mô đun tổng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như nums =[1,2,3] queries =[[1,1,3], [2,1,3]], thì đầu ra sẽ là [5, 4] vì đầu tiên phần tử nó là (1 XOR (1 XOR 2)) + (1 XOR (1 XOR 3)) + (1 XOR (2 XOR 3)) =5, tương tự đối với truy vấn thứ hai, nó là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7
• N:=kích thước của nums
• q_cnt:=kích thước của các truy vấn
• C:=một danh sách mới
• res:=một danh sách mới
• đối với tôi trong phạm vi từ 0 đến 19, hãy thực hiện
  • R:=một mảng có một phần tử 0
  • t:=0
  • đối với mỗi x trong nums, thực hiện
    • t:=t + (x sau khi dịch chuyển i lần sang phải) VÀ 1
    • chèn t vào cuối R
  • chèn R vào cuối C
• đối với j trong phạm vi 0 đến q_cnt, thực hiện
  • (K, P, R):=truy vấn [j]
  • d:=R - P + 1
  • t:=0
  • đối với tôi trong phạm vi từ 0 đến 19, hãy thực hiện
    • n1:=C [i, R] - C [i, P-1]
    • n0:=d - n1
    • if (K sau khi dịch chuyển i lần sang phải) VÀ 1 khác 0, thì
      • x:=thương số của (n1 * (n1 - 1) + n0 * (n0 - 1)) / 2
    • nếu không,
      • x:=n1 * n0
    • t:=(t + (x sau khi dịch chuyển i lần sang trái)) mod m
  • chèn t vào cuối res
• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(nums, queries):
    m = 10**9 + 7
    N = len(nums)
    q_cnt = len(queries)
    C = []
    res = []
    for i in range(20):
        R = [0]
        t = 0
        for x in nums:
            t += (x >> i) & 1
            R.append(t)
        C.append(R)
    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))

Đầu vào

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

Đầu ra

[5, 4]