06/04/2025 23:52:59

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2753. Зельеделие

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Профессор зельеделия Эзоп Шарп страдает от бессонницы и вынужден каждый день готовить себе сонное зелье. Сила зелья равна сумме сил добавленных в него ингредиентов и должна быть не меньше $L$ (чтобы заснуть вечером), но и не больше $U$ (чтобы вовремя проснуться утром). К счастью, в кладовой Хогвартса найдутся в изобилии ингредиенты с любой силой от 1 до $10^5$ , причем любые 2 разных вида ингредиентов имеют разную силу. Во избежание побочных эффектов от передозировки, один и тот же ингредиент нельзя добавлять в одно зелье более чем дважды. К сожалению, зелья вызывают привыкание: если выпить зелье с тем же составом ещё раз, оно не подействует. Сколько же дней профессор Шарп сможет справляться с бессоницей? Если число слишком большое, достаточно найти остаток от его деления на $10^9+9$ .

В единственной строке ввода содержатся два целых числа $L$ и $U$ ( $1 <= L <= U <= 10^5$ ) – минимальная и максимальная сила зелья.

Вывести одно целое число – остаток от деления количества подходящих сонных зелий на $10^9+9$ .

Пример ввода

3 4

Пример вывода

Пояснение к примеру: Можно составить два зелья силы 3: из одного ингредиента силы 3, либо двух ингредиентов с силами 1 и 2. Также можно составить четыре зелья силы 4 из таких наборов ингредиентов: 4; 1+3; 1+1+2; 2+2. Зелья 1+1+1 и 1+1+1+1 использовать нельзя из-за передозировки ингредиента с силой 1.

19/03/2023	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8)
23/03/2023	Prime Time (разбор, дорешивание) (проводит BOGAT) (F)
12/07/2023	Лето 2023-8 сложные (F)
10/07/2024	Лето 2024-8 сложные (F)
29/11/2024	ICPC Bedolagi (проводит BOGAT) (D)