在Python中找给定数字列表的所有查询的kpr sum的程序

假设我们有一个数字列表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：=新列表
对于i在0到19的范围内，执行以下操作 –
- R：=具有单个元素0的数组
- t：=0
- 对于nums中的每个x，执行以下操作 –
  - t：= t + (在右移i次后的x) AND 1
  - 将t插入R的末尾
- 将R插入C的末尾
对于j在0到q_cnt的范围内，执行以下操作 –
- (K，P，R)：=查询[j]
- d：= R-P + 1
- t：= 0
- 对于i在0到19的范围内，执行以下操作 –
  - n1：= C [i，R] -C [i，P-1]
  - n0：= d – n1
  - 如果(K在右移i次后)AND 1为非零，则 –
  - x：= (n1 *（n1-1）+ n0 *（n0-1）)/ 2的商
  - 否则，
  - x：= n1 * n0
  - t：=（t +（在左移i次后的x））mod m
- 将t插入res的末尾
返回res

例子

让我们看一下以下实现，以更好地了解−

def solve(nums, queries):
    m = 10 ** 9 + 7
    N = len(nums)
    q_cnt = len(queries)
    C = []
    res = []
    for i inrange(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))