Overview

For a sequence of length \(N\), compute the product of each contiguous subarray (of length \(K\)), then calculate the sum of all these products modulo \(10^9+7\).

Analysis

If we naively compute the product of each interval \([i, i+K-1]\), each interval requires \(K\) multiplications, giving a total of \(O((N-K+1)K)\). Given the constraint \(N \le 2\times 10^5\), cases like \(N=K=2\times 10^5\) would be far too slow.

The key observation here is that the products of adjacent intervals are “almost the same.”

• Let \(P_i\) be the product of the interval \([i, i+K-1]\).
• The product \(P_{i+1}\) of the next interval \([i+1, i+K]\) is obtained by:
  • Removing the leading element \(A_i\)
  • Adding the new trailing element \(A_{i+K}\)

In other words, [ P_{i+1} = P_i \div Ai \times A{i+K} ]

However, in the world of modular arithmetic, “division” cannot be performed directly, so we use modular inverses to update as follows: [ P_{i+1} \equiv P_i \times Ai^{-1} \times A{i+K} \pmod{MOD} ]

In this problem, since \(A_i \le 10^9\) and \(MOD=10^9+7\), all \(A_i\) satisfy \(0 \not\equiv A_i \pmod{MOD}\), so the modular inverse always exists.

Algorithm

1. Compute the product of the first interval \([1, K]\): [ P_1 = A_1 A_2 \cdots A_K \bmod MOD ] and add it to the answer \(ans\).
2. For \(i=2\) to \(N-K+1\), update from the previous product:
   • The element being removed is \(A_{i-1}\)
   • The element being added is \(A_{i+K-1}\) [ Pi \equiv P{i-1} \times (A{i-1})^{-1} \times A{i+K-1} \pmod{MOD} ] Compute this and add it to \(ans\).
3. Since MOD is prime, the modular inverse can be computed using Fermat’s little theorem: [ x^{-1} \equiv x^{MOD-2} \pmod{MOD} ] This is calculated as pow(x, MOD-2, MOD).
4. To avoid computing the inverse of the same value multiple times, cache the results using a dictionary (inv_cache in the code).

(Example) For \(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\) Output the sum \(6+15+35=56\) modulo MOD. In the implementation, division is replaced with multiplication by the modular inverse.

Complexity

• Time complexity: \(O(N \log MOD)\)
  (Each interval update is \(O(1)\), but the inverse computation pow is \(O(\log MOD)\) in the worst case. Caching ensures the inverse of each distinct value is computed only once.)
• Space complexity: \(O(N)\)
  (For the array \(A\) and the inverse cache.)

Implementation Notes

• Division under MOD is not possible directly, so always use “multiply by the modular inverse” instead.

• In this problem, since \(A_i < MOD\) and \(A_i \ge 1\), the modular inverse always exists and is safe to use.

• Update with MOD at every step, such as prod = prod * inv(A[i-1]) % MOD, to prevent overflow and value explosion.

• Since inverse computation is expensive, caching via inv_cache is effective.

  Source Code

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()

This editorial was generated by gpt-5.2-high.