概要

長さ \(N\) の数列について、各連続区間（長さ \(K\)）の積をすべて求め、その総和を \(10^9+7\) で割った余りとして計算します。

考察

各区間 \([i, i+K-1]\) の積をそのまま計算すると、1 区間あたり \(K\) 回の掛け算が必要で、合計で \(O((N-K+1)K)\) になります。制約では \(N \le 2\times 10^5\) なので、例えば \(N=K=2\times 10^5\) のようなケースでは到底間に合いません。

ここで重要な気づきは、隣り合う区間の積は「ほとんど同じ」だということです。

• 区間 \([i, i+K-1]\) の積を \(P_i\) とすると、
• 次の区間 \([i+1, i+K]\) の積 \(P_{i+1}\) は、
  • 先頭の \(A_i\) が抜けて
  • 新しく末尾の \(A_{i+K}\) が入る

つまり、 [ P_{i+1} = P_i \div Ai \times A{i+K} ] となります。

ただし、MOD を取った世界では「割り算」はそのままではできないので、逆元を使って [ P_{i+1} \equiv P_i \times Ai^{-1} \times A{i+K} \pmod{MOD} ] と更新します。

この問題では \(A_i \le 10^9\) かつ \(MOD=10^9+7\) なので、すべての \(A_i\) は \(0 \not\equiv A_i \pmod{MOD}\) を満たし、逆元が必ず存在します。

アルゴリズム

1. 最初の区間 \([1, K]\) の積 [ P_1 = A_1 A_2 \cdots A_K \bmod MOD ] を計算し、答え \(ans\) に加える。
2. \(i=2\) から \(N-K+1\) まで順に、直前の積から更新する：
   • 抜ける要素は \(A_{i-1}\)
   • 入る要素は \(A_{i+K-1}\) [ Pi \equiv P{i-1} \times (A{i-1})^{-1} \times A{i+K-1} \pmod{MOD} ] を計算し、\(ans\) に加える。
3. 逆元は MOD が素数なのでフェルマーの小定理より [ x^{-1} \equiv x^{MOD-2} \pmod{MOD} ] として pow(x, MOD-2, MOD) で求める。
4. 同じ値の逆元を何度も計算しないよう、辞書でキャッシュする（コード中の inv_cache）。

（例） \(A=[2,3,5,7], K=2\) のとき、 - \(P_1=2\cdot 3=6\) - \(P_2=6\div 2 \cdot 5 = 15\) - \(P_3=15\div 3 \cdot 7 = 35\) これらの和 \(6+15+35=56\) を MOD で出力します。実装では割り算を逆元で置き換えます。

計算量

• 時間計算量: \(O(N \log MOD)\)
  （各区間更新は \(O(1)\) だが、逆元計算 pow が最悪で \(O(\log MOD)\)。キャッシュにより同じ値の逆元は 1 回で済む）
• 空間計算量: \(O(N)\)
  （配列 \(A\) と、逆元キャッシュ）

実装のポイント

• MOD 下での割り算はできないので、必ず「逆元を掛ける」形にする。

• 今回は \(A_i < MOD\) かつ \(A_i \ge 1\) なので、逆元が常に存在して安全。

• prod = prod * inv(A[i-1]) % MOD のように、毎回 MOD を取りながら更新してオーバーフローや値の肥大化を防ぐ。

• 逆元計算は重いので、inv_cache によるキャッシュが有効です。

  ソースコード

import sys

MOD = 10**9 + 7

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    inv_cache = {}

    def inv(x):
        v = inv_cache.get(x)
        if v is None:
            v = pow(x, MOD - 2, MOD)
            inv_cache[x] = v
        return v

    prod = 1
    for i in range(K):
        prod = (prod * A[i]) % MOD

    ans = prod
    for i in range(1, N - K + 1):
        prod = (prod * inv(A[i - 1])) % MOD
        prod = (prod * A[i + K - 1]) % MOD
        ans = (ans + prod) % MOD

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。