Счастливые в диапазоне
Билеты пронумерованы числами из 2n цифр, с ведущими нулями: при n = 3 первый билет — 000000, последний — 999999. Билет счастливый, если сумма первых n цифр равна сумме последних n. Для каждого запроса — сколько счастливых билетов с номерами от L до R включительно.
Вход
В первой строке n и q (1 ≤ n ≤ 9, 1 ≤ q ≤ 5 · 10⁴). Дальше q строк: L и R (0 ≤ L ≤ R < 10²ⁿ), записанные без ведущих нулей.
Выход
Для каждого запроса — число счастливых билетов в отдельной строке. Оно меньше 10¹⁷.
Примеры
Пример 1
3 5 0 999999 123456 654321 700000 700999 123456 123456 123501 123501
55252 31607 36 0 1
Пример 2
1 4 0 99 10 20 55 55 0 0
10 1 1 1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Ответ для [L, R] — разность ответов для [0, R] и [0, L − 1]. Как сосчитать счастливые номера от 0 до x, не перебирая их?
2Подсказка 2
Номер меньше x, если на первой позиции, где они расходятся, его цифра меньше. Значит, номера можно разбить на пачки «совпадает с x до позиции i, на позиции i цифра d меньше, дальше что угодно». Сколько счастливых в такой пачке, зависит только от сумм уже поставленных цифр.
3Идея
Динамика по цифрам. Таблица ways[r][b] — сколькими способами записать r цифр с суммой b. Пачка в правой половине: левая набрала a, правая уже c + d, и оставшимся r цифрам нужно дать a − c − d — это ways[r][…]. Пачка в левой половине: левая набрала s, свободны ещё r цифр левой и вся правая — счастливых Σt ways[r][t] · ways[n][s + t].
4Разбор
Запросов до 5 · 10⁴, по два прохода на запрос. Чтобы проход стоил O(n), а не O(10n · 9n), заранее посчитаем для левой половины числа H[r][s] и их префиксные суммы по s: цифры d = 0 … xi − 1 дают подряд идущие s, и их вклад — одна разность. Для правой половины — префиксные суммы самих ways[r]. Если на пути «впритык» разность сумм ушла в минус, дальше ни одного счастливого нет.
4+Решение
5Сложность
Подготовка — O(n³ · 100), запрос — O(n). Числа не больше 3,3 · 10¹⁶ — помещаются в 64 бита.
6Типичные ошибки
- Перебор номеров. Это
wrong.py: на коротких диапазонах шестизначных билетов он успевает, но уже в четвёртом тесте диапазоны шире, а в пятом номера восемнадцатизначные. - Забыть сам R. Пачки считают номера строго меньше x; x проверяется в конце пути.
- L = 0. Ответ до −1 — ноль.
- Номер без ведущих нулей. Во входе 123 при n = 3 — это билет 000123: дополните его нулями до 2n цифр.