Overview

Given a sequence of length \(N\), consider all ways to choose \(K\) consecutive elements. Compute the product of the chosen elements for each way, and output the sum of all these products modulo \(10^9 + 7\).

Analysis

In this problem, we need to compute the product of every \(K\) consecutive elements and calculate their sum. A naive approach would be, for each starting position \(i\), to multiply the \(K\) elements from \(A_i\) to \(A_{i+K-1}\) one by one. However, this method takes \(O(K)\) per product computation, resulting in an overall time complexity of \(O((N-K+1) \cdot K)\), which is \(O(N^2)\) in the worst case. This is too slow for the constraint \(N \leq 2 \times 10^5\) (TLE).

Therefore, we need an efficient way to compute the product of consecutive subsequences. This can be solved using prefix products. A prefix product is a technique where we precompute the product from the beginning, allowing us to quickly compute the product of any interval.

For example, if we define the prefix product of the sequence \(A = [a_1, a_2, a_3, a_4]\) as \(P[i] = a_1 \times a_2 \times \cdots \times a_i\), then the product of the interval \([L, R]\) can be computed as follows:

\[ \text{prod}(L, R) = \frac{P[R]}{P[L-1]} \]

However, in modular arithmetic, division is not ordinary division — it must be expressed as multiplication using the modular inverse.

Therefore, by precomputing prefix products and their inverses, we can compute each interval’s product in \(O(1)\), bringing the overall time complexity to \(O(N)\).

Algorithm

1. Prefix product preprocessing
   • Precompute prefix_prod[i] := \(A_1 \times A_2 \times \cdots \times A_i\) (taking mod along the way)
2. Inverse prefix product preprocessing
   • Precompute suffix_inv_prod[i] := \((A_i \times A_{i+1} \times \cdots \times A_{N})^{-1}\) from back to front
3. Computing each interval’s product
   • For each \(i = 0, 1, ..., N-K\), compute the product of the interval \([i, i+K-1]\) as follows: $\( \text{prod} = \text{prefix\_prod}[i+K] \times \text{modinv}(\text{prefix\_prod}[i], MOD) \)$
   • Add this product to the answer (taking mod along the way)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Managing the prefix product array with 1-based indexing simplifies boundary conditions.

• The modular inverse is computed using pow(a, MOD - 2, MOD) (by Fermat’s little theorem, \(a^{p-2} \equiv a^{-1} \pmod{p}\)).

• When computing interval products, if prefix_prod[i] is 0, the inverse does not exist, so caution is needed. However, in this problem all inputs are positive integers, so this is not an issue.

  Source Code

MOD = 10**9 + 7

def modinv(a, mod):
    return pow(a, mod - 2, mod)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 累積積を前処理で求める
    # 累積積の添字は1-basedで扱う
    prefix_prod = [1] * (N + 1)
    for i in range(N):
        prefix_prod[i + 1] = (prefix_prod[i] * A[i]) % MOD

    # 逆元の累積積も前処理で求める
    suffix_inv_prod = [1] * (N + 1)
    for i in range(N - 1, -1, -1):
        suffix_inv_prod[i] = (suffix_inv_prod[i + 1] * modinv(A[i], MOD)) % MOD

    result = 0
    # 各連続部分列の積を計算して加算
    for i in range(N - K + 1):
        # [i, i+K-1] の積 = prefix_prod[i+K] * modinv(prefix_prod[i], MOD)
        prod = (prefix_prod[i + K] * modinv(prefix_prod[i], MOD)) % MOD
        result = (result + prod) % MOD

    print(result)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.