Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
У `K` людей есть общий массив из `N` целых чисел. Любой его подмассив от `L` до `R` (то есть элементы, стоящие в позициях от `L` до `R` включительно, `1<=L<=R<=N`) они делят между собой следующим образом:
- первое число достается первому человеку,
- второе число -- второму человеку,
- ...,
- `K`-тое число достается `K`-тому человеку,
- `K+1`-ое число -- снова первому,
- `K+2`-ое число -- снова второму,
- и так далее по кругу.
При этом длина подмассива не обязательно делится на `K`, то есть разные люди могут получить разное количество чисел.
Если после деления подмассива суммы чисел у всех людей оказались равны друг другу, то такой подмассив называют справедливым.
Подсчитайте, сколько различных справедливых подмассивов можно выбрать из заданного массива. Подмассивы считаются различными,
если отличаются их левые или правые границы.
В первой строке ввода содержатся два целых числа: `N` -- размер массива (`1<=N<=10^5`) и `K` -- количество людей (`2<=K<=5`).
Во второй строке ввода содержатся `N` целых чисел `a_i` -- элементы массива (`-10^9 <= a_i <= 10^9`).
Выведите единственное целое число -- количество справедливых подмассивов.
```sample Пример ввода
7 2
1 2 1 3 4 1 1
```
```sample Пример вывода
6
```
Пояснение к примеру 1. Справедливыми являются следующие подмассивы:
от 6 до 7 - [1 1],
от 1 до 3 - [1 2 1],
от 4 до 6 - [3 4 1],
от 2 до 5 - [2 1 3 4],
от 1 до 6 - [1 2 1 3 4 1],
от 2 до 7 - [2 1 3 4 1 1].
В каждом из этих подмассивов сумма элементов, стоящих на четных местах, равна сумме элементов, стоящих на нечетных местах.
```sample Пример ввода
2 2
0 0
```
```sample Пример вывода
3
```
Пояснение к примеру 2. Cправедливыми являются все подмассивы: от 1 до 1 - [0], от 2 до 2 - [0], От 1 до 2 - [0, 0].
Система оценки и описание подзадач
||.u|Подзадача 1 (20 баллов)||
`N<=100`, `K=2`, `-10 <= a_i <= 10`
||.u|Подзадача 2 (20 баллов)||
`N<=1500`, `K=2`, `-10 <= a_i <= 10`
Необходимые подзадачи: 1.
||.u|Подзадача 3 (20 баллов)||
`N<=10^5`, `K=2`, `-10 <= a_i <= 10`
Необходимые подзадачи: 1, 2.
||.u|Подзадача 4 (20 баллов)||
`N<=10^5`, `K=2`, `-10^9 <= a_i <= 10^9`
Необходимые подзадачи: 1, 2, 3.
||.u|Подзадача 5 (20 баллов)||
Ограничения из условий задачи.
Необходимые подзадачи: 1, 2, 3, 4
Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается о первой ошибке.
Начало
Рабочее место участника
Предрасчеты, кэширование вычислений