题目描述

$N$ 個の箱が左右一列に並んでおり、左から $i$ 番目の箱には $A_i$ 個のお菓子が入っています。

あなたは、連続したいくつかの箱からお菓子を取り出して $M$ 人の子供たちに均等に配りたいと考えています。

そこで、以下を満たす組 $(l,\ r)$ の総数を求めてください。

• $l,\ r$ はともに整数であり $1\ \leq\ l\ \leq\ r\ \leq\ N$ を満たす
• $A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r$ は $M$ の倍数である

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $A_2$ $...$ $A_N$

输出格式

条件を満たす組 $(l,\ r)$ の総数を出力せよ。

出力の際には、出力が $32$ ビットの整数型に収まらない可能性があることに注意せよ。

题目大意

有 $n$ 个盒子排成一排，其中左数第 $i$ 个盒子里面有 $a_i$ 个气球。你现在需要从一段连续的盒子当中取出所有的糖果，然后均匀地分给 $m$ 个小朋友。你希望最终每个小朋友手上的糖果数量相同，因此，你思考着有多少组连续的盒子里面的糖果数量是 $m$ 的倍数。形式化地说，你想找到一共有多少个二元组 $(l,r)$ 满足如下要求：

• $1\leqslant l\leqslant r\leqslant n$。
• $\sum\limits_{i=l}^r a_i\mid m$。

数据范围：

• $1\leqslant n\leqslant 10^5$，$2\leqslant m\leqslant 10^9$。
• $1\leqslant a_i\leqslant 10^9$。

Translated by Eason_AC
2021.12.27

3 2
4 1 5

3

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

提示

制約

• 入力は全て整数である
• $1\ \leq\ N\ \leq\ 10^5$
• $2\ \leq\ M\ \leq\ 10^9$
• $1\ \leq\ A_i\ \leq\ 10^9$

Sample Explanation 1

各組 $(l,\ r)$ に対する和 $A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r$ は次のとおりであり、このうち $3$ つが $2$ の倍数です。 - $(1,\ 1)$ に対する和: $4$ - $(1,\ 2)$ に対する和: $5$ - $(1,\ 3)$ に対する和: $10$ - $(2,\ 2)$ に対する和: $1$ - $(2,\ 3)$ に対する和: $6$ - $(3,\ 3)$ に対する和: $5$