/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 ビットの整数型に収まらない可能性があることに注意せよ。
入力例 1
3 2 4 1 5
出力例 1
3
各組 (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
入力例 2
13 17 29 7 5 7 9 51 7 13 8 55 42 9 81
出力例 2
6
入力例 3
10 400000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
25
Score : 400 points
Problem Statement
There are N boxes arranged in a row from left to right. The i-th box from the left contains A_i candies.
You will take out the candies from some consecutive boxes and distribute them evenly to M children.
Such being the case, find the number of the pairs (l, r) that satisfy the following:
- l and r are both integers and satisfy 1 \leq l \leq r \leq N.
- A_l + A_{l+1} + ... + A_r is a multiple of M.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 2 \leq M \leq 10^9
- 1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
Output
Print the number of the pairs (l, r) that satisfy the conditions.
Note that the number may not fit into a 32-bit integer type.
Sample Input 1
3 2 4 1 5
Sample Output 1
3
The sum A_l + A_{l+1} + ... + A_r for each pair (l, r) is as follows:
- Sum for (1, 1): 4
- Sum for (1, 2): 5
- Sum for (1, 3): 10
- Sum for (2, 2): 1
- Sum for (2, 3): 6
- Sum for (3, 3): 5
Among these, three are multiples of 2.
Sample Input 2
13 17 29 7 5 7 9 51 7 13 8 55 42 9 81
Sample Output 2
6
Sample Input 3
10 400000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
25