E - 余数和个数相等

得分：500

问题描述

给定一个由 $N$ 个正整数组成的序列 $A_1, A_2, ..., A_N$ 和一个正整数 $K$。

求出满足以下条件的 $A$ 的非空连续子序列的数量：将子序列的元素之和除以 $K$ 的余数等于子序列的元素个数。即使两个序列相等，只要它们的位置不同，我们也认为它们是不同的子序列。

约束条件

• 输入的所有值都是整数。
• $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$

输出

打印满足条件的子序列的数量。

5 4
1 4 2 3 5

4

满足条件的子序列有：$(1)$, $(4,2)$, $(1,4,2)$ 和 $(5)$。

8 4
4 2 4 2 4 2 4 2

7

$(4,2)$ 被计算了四次，$(2,4)$ 被计算了三次。

10 7
14 15 92 65 35 89 79 32 38 46

8