Pythonの配列内の等間隔の要素の合計を見つけるプログラム

正の整数を含むサイズnの配列'nums'があるとします。整数のペア（pi、qi）を含む別の配列「クエリ」があります。配列クエリ内のすべてのクエリについて、答えは配列nums [j]内の数値の合計になります。ここで、pi <=j

したがって、入力がnums =[2、3、4、5、6、7、8、9、10]のようである場合、クエリ=[（2、5）、（7、3）、（6、4）] 、出力は[13、9、8]になります。

これを解決するには、次の手順に従います-

• A：=nums

• Q：=クエリ

• n：=numsの長さ

• M：=10 ^ 9 + 7

• m：=（n ^ 0.5）+2の整数値

• P：=リストを含む新しいリストAm回

• 1からmの範囲のiの場合、実行します

  • n-1から-1の範囲のjについては、1ずつ減らします。

    • i + j

      • P [i、j]：=（P [i、j] + P [i、i + j]）モジュロM

• Qの値b、kごとに、実行

  • k

    • [インデックスP[k、b]からの値]

      を返します

  • それ以外の場合

    • return [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]