用 Python 编写程序，找出数组中等距元素的总和
pythonserver side programmingprogramming更新于 2025/12/13 23:40:17
假设有一个大小为 n 的数组"nums"，其中包含正整数。我们还有另一个数组"queries"，其中包含整数对 (pi, qi)。对于数组查询中的每个查询，答案将是数组 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 的长度
M := 10^9 + 7
m := (n ^ 0.5) + 2
P := 一个包含列表 A m 次的新列表
对于范围在 1 到 m 内的 i，执行
对于范围在 n-1 到 -1 内的 j，减少 1，执行
如果 i+j < n，则
P[i, j] := (P[i, j]+P[i, i+j]) modulo M
对于 Q 中的每个值 b、k，执行
如果 k < m，则
返回 [索引 P[k, b] 的值]
否则
返回 [sum(A[b to k]) modulo 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]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
