在Python中找出数组中等间距元素的和的程序

假设有一个大小为n的正整数数组’nums’。我们有另一个包含整数对(pi, qi)的数组’queries’。对于数组查询中的每个查询，答案将是数组nums[j]中满足pi <= j < n并且(j-pi)可被qi整除的数字的总和。我们必须返回所有这些查询的答案，如果是一个大值，则返回模10^9 + 7的答案。

因此，如果输入为nums = [2, 3, 4, 5, 6, 7, 8, 9, 10]，queries = [(2, 5)，(7, 3)，(6, 4)]，则输出将是[13, 9, 8]。

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

• A:=nums

• Q:=queries

• n:=nums的length

• M:=10^9 + 7

• m:= (n ^ 0.5)+2的整数值

• P:=包含列表A的新列表m次

• 对于i在范围1到m内，执行以下操作

  • 对于从n-1到-1的j，逐渐减少1，执行以下操作
    • 如果i+j
    • 对于P[i,j] := (P[i,j]+P[i,i+j])模M
• 对于每个值b，k in Q，执行以下操作
  • 如果k
    • 返回[index P[k,b]的值]
  • 否则
    • 返回[sum(A[b to k])模M]

示例

让我们看下面的实现，以更好地理解 –

def solve(A, Q):
   n, M = len(A), 10**9+7
   m = int(n**0.5)+2
   P = [A[:] for _ in range(m)]
   for i in range(1,m):
      for j in range(n-1,-1,-1):
         if i+j < n:
            P[i][j] = (P[i][j]+P[i][i+j]) % M
   return [P[k][b] if k < m else sum(A[b::k]) % M for b, k in Q]

print(solve([2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]))

输入

[2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]

输出

[13, 9, 8]