Ральф и арифметика

Пусть $$$l_n$$$ — длина десятичной записи числа $$$n$$$.

Посчитаем количество чисел без второстепенных цифр длины $$$l = 1, 2, \ldots l_n - 1$$$. Всего у нас $$$k$$$ второстепенных цифр, значит всего у нас $$$10 - k$$$ разрешенных цифр. Также первая цифра не может быть нулем, значит вариантов первой цифры либо $$$f = 10 - k$$$, если $$$0$$$ — второстепенная цифра, либо $$$f = 9 - k$$$ иначе. Тогда ответ для фиксированной длины $$$l$$$ равен $$$f \cdot (10 - k)^{l-1}$$$.

Теперь посчитаем количество чисел без второстепенных цифр длины $$$l_n$$$. Все такие числа не превосходят $$$n$$$. Рассмотрим число $$$n$$$ отдельно: прибавим $$$1$$$ к ответу, если в записи числа $$$n$$$ нет второстепенных цифр. Осталось рассмотреть числа длины $$$l_n$$$, строго меньшие $$$n$$$. У таких чисел есть несколько общих старших цифр с числом $$$n$$$ (возможно, $$$0$$$), затем идет цифра, меньшая соответствующей цифры числа $$$n$$$, а затем любые другие цифры. Переберем количество общих старших цифр с числом $$$n$$$: $$$p = 0 \ldots l_n - 1$$$. Если среди первых $$$p$$$ цифр числа $$$n$$$ есть второстепенная, то таких чисел нет. Иначе нужно найти $$$s$$$ — количество цифр, не являющихся второстепенными, строго меньшие $$$p$$$-й цифры числа $$$n$$$, и прибавить к ответу $$$s \cdot (10 - k)^{l_n - p - 1}$$$.