D - 糖果分配

得分：400分

问题描述

有$N$个盒子从左到右排成一行，第$i$个盒子中有$A_i$个糖果。

你将从一些连续的盒子中取出糖果，平均分给$M$个孩子。

在这种情况下，找到满足以下条件的数对$(l, r)$的数量：

• $l$和$r$都是整数，并且满足$1 \leq l \leq r \leq N$。
• $A_l + A_{l+1} + ... + A_r$是$m$的倍数。

限制

• 输入中的所有数值都是整数。
• $1 \leq N \leq 10^5$
• $2 \leq M \leq 10^9$
• $1 \leq A_i \leq 10^9$

输入

输入以以下格式从标准输入中给出：

$N$ $M$

$A_1$ $A_2$ $...$ $A_N$

输出

打印满足条件的数对$(l, r)$的数量。

请注意，该数可能无法适应32位整数类型。

3 2
4 1 5

3

每对$(l, r)$的和$A_l + A_{l+1} + ... + A_r$如下：

• $(1, 1)$的和：$4$
• $(1, 2)$的和：$5$
• $(1, 3)$的和：$10$
• $(2, 2)$的和：$1$
• $(2, 3)$的和：$6$
• $(3, 3)$的和：$5$

其中有三个是2的倍数。

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

6

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

25