/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の正整数からなる数列を持っています。数列の i 番目 (1 \leq i \leq N) の要素は A_i です。
高橋君は、この数列の 連続する K 個の要素からなる区間 をすべて考え、それぞれの区間に含まれる要素の積を求めたいと考えています。
連続する K 個の要素からなる区間は N - K + 1 通りあります。i = 1, 2, \ldots, N - K + 1 のそれぞれについて、i 番目から i + K - 1 番目までの K 個の要素からなる区間が取れます。
各区間に含まれる K 個の要素の積 A_i \times A_{i+1} \times \cdots \times A_{i+K-1} を計算し、すべての区間における積の総和、すなわち
\sum_{i=1}^{N-K+1} \prod_{j=i}^{i+K-1} A_j
を求めてください。
答えは非常に大きくなる可能性があるため、10^9 + 7 で割った余りを出力してください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、数列の長さを表す整数 N と、区間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、数列の各要素を表す N 個の正整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
すべての連続する K 個の要素からなる区間における積の総和を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 1
5 2 1 2 3 4 5
出力例 1
40
入力例 2
6 3 2 3 1 4 2 5
出力例 2
66
入力例 3
10 4 100 200 300 400 500 600 700 800 900 1000
出力例 3
799992244
Score : 366 pts
Problem Statement
Takahashi has a sequence of N positive integers. The i-th element (1 \leq i \leq N) of the sequence is A_i.
Takahashi wants to consider all intervals consisting of K consecutive elements of this sequence, and compute the product of the elements in each interval.
There are N - K + 1 intervals consisting of K consecutive elements. For each i = 1, 2, \ldots, N - K + 1, we can take the interval consisting of K elements from the i-th to the (i + K - 1)-th element.
Compute the product of the K elements in each interval, A_i \times A_{i+1} \times \cdots \times A_{i+K-1}, and find the sum of the products over all intervals, namely
\sum_{i=1}^{N-K+1} \prod_{j=i}^{i+K-1} A_j
Since the answer can be very large, output the remainder when divided by 10^9 + 7.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the length of the sequence and an integer K representing the length of the interval, separated by a space.
- The second line contains N positive integers A_1, A_2, \ldots, A_N representing the elements of the sequence, separated by spaces.
Output
Output in one line the remainder when the sum of products over all intervals consisting of K consecutive elements is divided by 10^9 + 7.
Sample Input 1
5 2 1 2 3 4 5
Sample Output 1
40
Sample Input 2
6 3 2 3 1 4 2 5
Sample Output 2
66
Sample Input 3
10 4 100 200 300 400 500 600 700 800 900 1000
Sample Output 3
799992244