Маршруты с круглой суммой

В городе Ровномайске вдоль одной длинной улицы стоят датчики. Каждый датчик за день собрал некоторое число «единиц шума».

Мэр любит круглые числа: маршрут подряд идущих кварталов считается удачным, если суммарный шум на этом отрезке делится на число k без остатка.

Найдите, сколько существует удачных маршрутов (то есть сколько подотрезков массива имеют сумму, кратную k).

Важно: суммы могут быть очень большими (до значений, не вмещающихся в 32-битный тип; как на олимпиадах). В Python это не проблема.

Формат ввода

В первой строке записаны два целых числа n и k. Во второй строке записаны n целых чисел a1, a2, ..., an — шум по кварталам.

Формат вывода

Выведите одно целое число — количество подотрезков, сумма на которых делится на k.

Ограничения

• 1 ≤ n ≤ 20000
• 1 ≤ k ≤ 1 000 000
• 0 ≤ ai ≤ 1 000 000

Пример

Ввод:

5 3
1 2 3 4 1

Вывод:

4

Ключевое наблюдение: сумма на отрезке [l..r] равна pref[r] - pref[l-1], где pref[i] — сумма первых i элементов. Эта сумма делится на k тогда и только тогда, когда pref[r] % k == pref[l-1] % k. То есть каждый «удачный маршрут» соответствует паре префиксов с одинаковым остатком.

Почему работает приём: вместо перебора всех O(n^2) подотрезков мы идём слева направо и считаем, сколько раз уже встречался текущий остаток. Каждый прошлый такой остаток даёт новый подотрезок, заканчивающийся в текущей позиции.

План:

• Заведи переменные: pref = 0, ans = 0.
• Заведи структуру cnt, где cnt[r] = сколько префиксов имели остаток r. Важно сразу положить cnt[0] = 1 (пустой префикс).
• Для каждого числа x:
• обнови остаток префикса: pref = (pref + x) % k.
• добавь к ответу cnt[pref] (столько подотрезков заканчиваются здесь и делятся на k).
• увеличь cnt[pref] на 1.
• Выведи ans.

Сложность: O(n) по времени и O(min(n, k)) по памяти (храним только встреченные остатки; удобно через dict, особенно когда k большой).

Частая ошибка: забыть про cnt[0] = 1 — тогда не посчитаются отрезки, начинающиеся с первого элемента.