Ctrl K

Слипшаяся распечатка чисел

Сложная
Программа должна была напечатать список целых чисел через пробел, но пробелы потерялись, и получилась одна строка цифр digits. Известно, что каждое число списка лежало в диапазоне от 1 до limit и было записано без ведущих нулей. Сколько разных списков могли превратиться в строку digits? Ответ может быть большим, верните его по модулю 10⁹ + 7.
Пример 1
digits="2105", limit=30 → 1

Ноль не может быть отдельным числом и не может начинать число, поэтому он идёт только в паре с единицей: [2, 10, 5]. Это единственный вариант.

Пример 2
digits="1111", limit=11 → 5

Разбиения: [1, 1, 1, 1], [11, 1, 1], [1, 11, 1], [1, 1, 11], [11, 11] — всего 5.

Пример 3
digits="700", limit=99 → 0

Нули не могут стоять ни отдельно, ни в начале числа, а 700 больше 99 — разбиений нет.

Ограничения
  • 1 ≤ len(digits) ≤ 10⁵
  • digits состоит только из цифр и не начинается с 0
  • 1 ≤ limit ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиШаблон с точкой и звёздочкой СложнаяСамый длинный сбалансированный отрезок скобок СложнаяПодходит ли строка под шаблон СложнаяПеретасовка разрезами СложнаяСколькими способами вычеркнуть Сложная
загружаем Python…
Вход
digits="2105", limit=30
Ожидается
1

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