Python程序，用于查找给定数字列表中所有查询的kpr和

假设我们有一个数字列表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 + (x右移i位) AND 1
    • 将t插入到R的末尾
  • 将R插入到C的末尾
• 对于j从0到q_cnt，执行以下操作：
  • (K, P, R) := queries[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 +(x左移i位)) mod m
  • 将t插入到res的末尾
• 返回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))

输入

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

输出

[5, 4]

Arnab Chakraborty

更新于：2021年10月6日

246次浏览

开启你的职业生涯

通过完成课程获得认证

开始