Overview

Given a sequence \(A\) of length \(N\), there are \(N-K+1\) ways to extract \(K\) consecutive elements. For each of these patterns, we compute the “total product of the selected elements,” and the problem asks for the sum of all these products modulo \(10^9 + 7\).

Analysis

Naive Approach and Its Limitations

If we naively multiply \(K\) elements for each interval, it takes \(O(K)\) computation per interval. Since there are \(N-K+1\) intervals, the total complexity is \(O(N \times K)\). Given the constraints \(N, K \leq 2 \times 10^5\), the worst case requires about \(4 \times 10^{10}\) operations, which will not finish within the time limit.

Using Prefix Products

Just as “prefix sums” can be used to efficiently compute interval “sums,” interval “products” can also be sped up using Prefix Products. We prepare an array \(P\) that stores the product from the beginning of sequence \(A\). - \(P_0 = 1\) - \(P_i = A_1 \times A_2 \times \dots \times A_i \pmod{10^9+7}\)

Using this, the product of the interval \([i, i+K-1]\) can be expressed as: $\(\prod_{j=i}^{i+K-1} A_j = P_{i+K-1} \div P_{i-1} \pmod{10^9+7}\)$

Using Modular Inverses

In modular arithmetic, division is equivalent to “multiplying by the modular inverse.” Since \(10^9+7\) is prime and \(A_i \geq 1\) by the constraints, the prefix product never becomes \(0\). Therefore, we can compute the modular inverse of \(P_{i-1}\) using Fermat’s little theorem.

Computing the inverse individually for each interval would cost \(O(N \log (\text{mod}))\), but by computing the inverses of the prefix products in reverse order, we can obtain all of them in \(O(N)\).

Algorithm

1. Compute Prefix Products: Create an array pre where pre[i] stores the product of the first \(i\) elements of \(A\). (\(O(N)\))
2. Compute Inverses:
   • First, compute the inverse of the total product pre[N] using Fermat’s little theorem (pow(pre[N], mod - 2, mod)).
   • Then, using the relation inv_pre[i-1] = inv_pre[i] * A[i-1], compute the inverses of all prefix products in reverse order. (\(O(N)\))
3. Compute the Total Sum: For each starting position \(i\), compute pre[i+K] * inv_pre[i] and sum them all up. (\(O(N)\))

Complexity

• Time complexity: \(O(N)\)
  • Building the prefix products takes \(O(N)\), computing inverses takes \(O(N + \log (\text{mod}))\), and the final aggregation takes \(O(N)\).
• Space complexity: \(O(N)\)
  • Arrays are needed to store the prefix products and their inverses.

Implementation Notes

• Batch computation of inverses: Calling the pow function repeatedly inside a loop is expensive, so it is efficient to compute it only once at the end and then derive the rest through sequential multiplication.

• Handling large input: In Python, using sys.stdin.read().split() allows for fast reading of large amounts of numerical data.

• Index management: Creating the prefix product array with size \(N+1\) for a sequence of \(N\) elements makes it easy to handle the empty product (1) and results in cleaner implementation.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に処理するのに適しています
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 数列の長さ, K: 連続する要素の個数
    n = int(input_data[0])
    k = int(input_data[1])
    
    # A: 数列（0-indexedで管理）
    a = list(map(int, input_data[2:]))
    
    # 法とする素数
    mod = 10**9 + 7
    
    # 累積積（prefix product）を計算する
    # pre[i] は a[0] * a[1] * ... * a[i-1] の積を mod で割った余り
    pre = [1] * (n + 1)
    for i in range(n):
        pre[i+1] = (pre[i] * a[i]) % mod
        
    # 累積積の逆元を O(N) で一括計算する
    # 10^9 + 7 は素数であり、a_i は 1 以上 10^9 以下なので、累積積が 0 になることはない
    inv_pre = [1] * (n + 1)
    # フェルマーの小定理を用いて pre[n] の逆元を計算する
    inv_pre[n] = pow(pre[n], mod - 2, mod)
    # pre[i-1] の逆元は、pre[i] の逆元に a[i-1] を掛けることで求められる
    for i in range(n, 0, -1):
        inv_pre[i-1] = (inv_pre[i] * a[i-1]) % mod
        
    ans = 0
    # 連続する K 個の要素の積の総和を求める
    # 開始インデックス i は 0 から N-K まで
    for i in range(n - k + 1):
        # 連続する K 個の要素 a[i], a[i+1], ..., a[i+k-1] の積は、
        # (a[0]*...*a[i+k-1]) * (a[0]*...*a[i-1])^-1 と等しい
        # すなわち、pre[i+k] * inv_pre[i] で求められる
        current_product = (pre[i+k] * inv_pre[i]) % mod
        ans = (ans + current_product) % mod
        
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.