用Python找出数组中均匀间隔元素之和的程序
假设有一个包含正整数的大小为n的数组'nums'。我们有另一个包含整数对(pi,qi)的数组“查询”。对于数组查询中的每个查询,答案将是数组nums[j]中数字的总和,其中pi<=j<n并且(j-pi)可以被qi整除。我们必须返回所有此类查询的答案,如果它是一个大值,我们将返回模10^9+7的答案。
因此,如果输入类似于nums=[2,3,4,5,6,7,8,9,10],则查询=[(2,5),(7,3),(6,4)],那么输出将是[13,9,8]。
示例
让我们看看以下实现以获得更好的理解-
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]