/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
長さ N の正整数列 A_1, A_2, \ldots , A_N と正の整数 K が与えられます。
A の空でない連続する部分列であって、要素の和を K で割った余りが要素の数と等しくなるものの数を求めてください。ただし、2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。
制約
- 入力は全て整数である。
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \cdots A_N
出力
条件をみたす部分列の個数を出力してください。
入力例 1
5 4 1 4 2 3 5
出力例 1
4
(1), (4,2), (1,4,2), (5) の 4 つが条件をみたす部分列です。
入力例 2
8 4 4 2 4 2 4 2 4 2
出力例 2
7
(4,2) が 4 回、(2,4) が 3 回数えられています。
入力例 3
10 7 14 15 92 65 35 89 79 32 38 46
出力例 3
8
Score : 500 points
Problem Statement
Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.
Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
Print the number of subsequences that satisfy the condition.
Sample Input 1
5 4 1 4 2 3 5
Sample Output 1
4
Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).
Sample Input 2
8 4 4 2 4 2 4 2 4 2
Sample Output 2
7
(4,2) is counted four times, and (2,4) is counted three times.
Sample Input 3
10 7 14 15 92 65 35 89 79 32 38 46
Sample Output 3
8