DMOPC '17 Contest 1 P2 - Sharing Crayons

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Mimi is helping out at a daycare! There are M children and N boxes of crayons in a row, the i^\text{th} of which has c_i crayons. Mimi will choose a single contiguous section of crayon boxes to give to the children. In order to be fair, she also wants the total number of crayons in the subarray she chooses to be divisible by M so that it can be split equally. How many ways can she do this?


For all subtasks, 1 \le c_i \le 10^9.

Subtask 1 [20%]

1 \le N \le 100
1 \le M \le 10^9

Subtask 2 [20%]

1 \le N \le 2\,000
1 \le M \le 10^6

Subtask 3 [40%]

1 \le N \le 10^5
1 \le M \le 10^6

Subtask 4 [20%]

1 \le N \le 10^5
1 \le M \le 10^9

Input Specification

The first line will have two space separated integers, N and M.
The second line will have N space separated integers, c_1, c_2, \ldots, c_N.

Output Specification

A single integer, the number of subarrays which have a total which is a multiple of M. This number may overflow 32-bit numbers.

Sample Input

5 6
3 5 9 6 10

Sample Output


Explanation for Sample

The two subarrays with a sum divisible by 6 are [6] and [5, 9, 6, 10].


There are no comments at the moment.