Pythonで配列内の等間隔の要素の合計を求めるプログラム

正の整数からなるサイズ n の配列「nums」と、整数ペア (pi, qi) を要素とする配列「queries」が与えられるとします。各クエリに対する答えは、pi ≤ j < n を満たし、かつ (j − pi) が qi で割り切れるすべての添字 j についての nums[j] の総和です。すべてのクエリの答えを求めてください。ただし、答えが非常に大きな値になる可能性があるため、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 := int(n ** 0.5) + 2（ステップ幅のしきい値）
• P := A のコピーを m 個格納した二次元リストを作成
• i を 1 から m − 1 までループ：
  • j を n − 1 から 0 まで逆順にループ：
    • i + j < n のとき、P[i][j] := (P[i][j] + P[i][i+j]) mod M
• Q 内の各クエリ (b, k) に対して：
  • k < m の場合：事前計算済みの P[k][b] をそのまま返す（O(1) で取得可能）
  • k ≥ m の場合：sum(A[b::k]) mod M を直接計算して返す

ステップ幅 k が小さいクエリが大量にある場合、毎回素朴に合計を計算すると処理時間が膨大になります。そこで、あらかじめ「開始位置 b から k 間隔で要素を足し合わせた接尾辞和」を表 P に構築しておけば、小さいステップ幅のクエリには定数時間で答えられます。逆に k が大きい場合は、合計対象の要素数が最大でも n / k 個程度しかないため、直接計算しても十分に高速です。この工夫により、全体の計算量は O((n + q)√n) 程度に抑えられます。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

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]