Толя й чудові сторінки#33

Толя й чудові сторінки (Editorial)

Числа сягають 10^{12}, тому перебирати їх усі неможливо. Це класична задача на динаміку за цифрами.

Спершу зведемо задачу до однієї межі. Позначимо — кількість чудових чисел у відрізку . Тоді відповідь дорівнює F(b) - F(a-1).

Тепер порахуємо . Запишемо як рядок цифр і будуватимемо число зліва направо, зберігаючи такий стан:

  • — скільки цифр уже поставлено;

  • — чи збігається побудований префікс з префіксом (якщо так, наступна цифра обмежена зверху відповідною цифрою , інакше — дев'яткою);

  • — чи почалося вже саме число (потрібно, щоб коректно обробити провідні нулі для коротших чисел);

  • — остання поставлена цифра.

Перехід: перебираємо наступну цифру від до межі. Якщо число вже почалося, вимагаємо d \ge \mathrm{prev} — саме це й означає неспадання. Якщо ще не почалося, то d = 0 залишає число «не початим», а d \ge 1 починає його.

База: дійшовши до кінця рядка, повертаємо , якщо число почалося, і інакше.

Стани мемоізуються, їх лише 13 \cdot 2 \cdot 2 \cdot 10, а переходів — по десять, тому обчислення миттєве.

Відповідь може бути великою, але не критично — усе одно рахуйте у 64-бітному типі, як і саму межу 10^{12}.