用 Python 编写程序，针对给定的数字列表查找所有查询的 kpr sum

pythonserver side programmingprogramming更新于 2025/12/7 18:20:17

假设我们有一个数字列表 nums。我们还有一个查询列表，其中 queries[i] 包含三个元素 [k, p, r]，对于每个查询，我们都必须找到 kpr_sum。 kpr_sum 的公式如下。

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

如果总和太大，则返回总和模 10^9+7。

因此，如果输入为 nums = [1,2,3] queries = [[1,1,3],[2,1,3]]，则输出将为 [5, 4]，因为对于第一个元素，它是 (1 XOR (1 XOR 2)) + (1 XOR (1 XOR 3)) + (1 XOR (2 XOR 3)) = 5，第二个查询同样为 4。

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

m := 10^9 + 7
N := nums 的大小
q_cnt := 查询的大小
C := 一个新列表
res := 一个新列表
对于 0 到 19 范围内的 i，执行
- R := 一个包含单个元素 0 的数组
- t := 0
- 对于 nums 中的每个 x，执行
  - t := t + (x after向右移动 i 次)AND 1
  - 在 R 末尾插入 t
- 在 C 末尾插入 R
对于范围在 0 到 q_cnt 内的 j，执行
- (K, P, R) := queries[j]
- d := R - P + 1
- t := 0
- 对于范围在 0 到 19 内的 i，执行
  - n1 := C[i, R] - C[i, P-1]
  - n0 := d - n1
  - 如果(向右移动 i 次后的 K)AND 1 非零，则
    - x := 的商(n1 *(n1 - 1) + n0 *(n0 - 1))/2
  - 否则，
    - x := n1 * n0
  - t :=(t +(向左移动 i 次后的 x)) mod m
- 在 res 末尾插入 t
返回 res

示例

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

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))