Ctrl K

Строки из блоков нулей и единиц

Средняя
Строку собирают из пустой, много раз приписывая в конец один из двух блоков: либо zero_block символов '0' подряд, либо one_block символов '1' подряд. Блоки можно чередовать как угодно. Сколько различных строк длиной от min_len до max_len включительно можно так получить? Ответ может быть большим — верните его по модулю 10⁹ + 7.
Пример 1
min_len=2, max_len=2, zero_block=1, one_block=1 → 4

Блоки по одному символу, нужна длина ровно 2: подходят "00", "01", "10", "11". Ответ 4.

Пример 2
min_len=3, max_len=4, zero_block=2, one_block=3 → 2

Длины 3 можно достичь только строкой "111", длины 4 — только "0000". Ответ 2.

Пример 3
min_len=4, max_len=6, zero_block=1, one_block=2 → 26
Ограничения
  • 1 ≤ min_len ≤ max_len ≤ 10⁵
  • 1 ≤ zero_block, one_block ≤ min_len
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый длинный зеркальный кусок СредняяВсе правильные скобочные строки СредняяМеньше всего прыжков до конца СредняяСамая прибыльная серия дней СредняяДобраться до последней клетки Средняя
загружаем Python…
Вход
min_len=2, max_len=2, zero_block=1, one_block=1
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 43 теста на сервере, включая скрытые.