Алгоритмы и структуры данных

Подмассивы с суммой, делящейся на n

Дан массив из n чисел. Нужно определить, сколько подмассивов имеют сумму, которая делится на n.

Входные данные

Первая строка входных данных содержит два целых числа — n, количество элементов в массиве (1 ≤ n ≤ ).
В следующей строке находятся n целых чисел, разделённых пробелами, которые представляют собой элементы массива .

Выходные данные

Программа должна вывести единственное целое число — количество подмассивов, сумма которых делится на n.

Примеры

Входные данные
Выходные данные
5 5 2 3 4 6
6

Пояснение

  1. 5 2 3 4 6
  1. 5 2 3 4 6
  1. 5 2 3 4 6
  1. 5 2 3 4 6
  1. 5 2 3 4 6
  1. 5 2 3 4 6
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue