Задача 6. Интервальные тренировки ≡

Условие

В академии физической культуры разработали новый метод интервальных тренировок спортсменов. В соответствии с этим методом спортсмен должен тренироваться каждый день, однако рост нагрузки должен постоянно сменяться её снижением и наоборот.

План тренировки представляет собой набор целых положительных чисел a₁, a₂, …, a_m, где a_i описывает нагрузку спортсмена в i-й день. Любые два соседних дня должны иметь различную нагрузку: a_i ≠ a_i + 1. Чтобы рост нагрузки и её снижение чередовались, для i от 1 до m − 2 должно выполняться следующее условие: если a_i < a_i + 1, то a_i + 1 > a_i + 2, если же a_i > a_i + 1, то a_i + 1 < a_i + 2.

Суммарная нагрузка в процессе выполнения плана должна составлять n, то есть a₁ + a₂ + …  + a_m = n. Ограничения на количество дней в плане нет, m может быть любым, но нагрузка в первый день тренировок зафиксирована: a₁ = k.

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

Требуется написать программу, которая по заданным n и k определяет, сколько различных планов тренировок удовлетворяют описанным ограничениям, и выводит остаток от деления количества таких планов на число 10⁹ + 7.

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

В первой строке входных данных находятся целые числа n, k.

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

Выведите одно число: остаток от деления количества планов тренировок на 10⁹ + 7.

Ограничения

1 ≤ n ≤ 5000, 1 ≤ k ≤ n

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения к примерам

В первом примере подходят следующие планы: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].

Во втором примере единственный подходящий план [3].

Примеры тестов

6 2

4

3 3

1

Разбор

Для решения подзадачи 1 можно применить рекурсивный перебор вариантов.

Тот же метод решает и подзадачу 2 при использовании аккуратного перебора с отсечениями. Если для n порядка 30 перебор не успевает найти ответ за отведенное ограничение по времени, можно применить метод предподсчёта: заранее на своём компьютере найти ответы для всех тестов с 1 ≤ k ≤ n ≤ 30 и отправить на проверку программу, которая выводит найденный заранее ответ.

Для решения подзадач 3 и 4 необходимо применить динамическое программирование. Рассмотрим сначала решение за O(n³), которое решает подзадачу 3.

Обозначим как up[n][k] количество планов тренировок, которые удовлетворяют описанным ограничениям, суммарная нагрузка которых равна n, нагрузка в первый день k, а нагрузка во второй день строго больше нагрузки в первый день. Аналогично введём величину down[n][k], для количества таких планов, где нагрузка во второй день строго меньше нагрузки в первый день.

Заметим, что up[n][n] = down[n][n] = 1. Для k < n значения можно вычислить по формулам:

up[n][k] = ∑n − ki = k + 1down[n − k][i],

down[n][k] = ∑k − 1i = 1up[n − k][i].

Величина, которую требуется найти по условию задачи, равна up[n][k] + down[n][k], не забудем также отдельный случай n = k, когда ответ равен 1.

Чтобы получить решение для подзадачи 4, для которой решение за O(n³) слишком медленное, можно использовать два подхода.

Подход 1: другая формула пересчёта. Заметим, что формула для up[n][k] отличается от up[n][k + 1] одним слагаемым: down[n − k][k + 1], поэтому up[n][k] = up[n][k + 1] + down[n − k][k + 1]. Аналогично, down[n][k] = down[n][k − 1] + up[n][k − 1]. Теперь значения вычисляются за O(1) и время подсчёта всех значений есть O(n²). Следует обратить внимание, что значения up[n][k] следует вычислять по убыванию k, а значения down[n][k] по возрастанию k.

Подход 2: префиксные суммы. Введем дополнительные величины:

sumUp[n][k] = ∑ki = 1up[n][i],

sumDown[n][k] = ∑ki = 1down[n][i].

Тогда up[n][k] = sumDown[n − k][n − k] − sumDown[n − k][k], down[n][k] = sumUp[n][k − 1].

Отметим, что во всех случаях следует аккуратно следить за тем, чтобы индексы значений, к которым происходит обращение в формулах, не выходили за пределы массивов и за порядком вычислений.