В этой задаче нужно было научиться отвечать на запрос количества красивых чисел от 1 до R.

Ясно, что чтобы проверить, делится ли число на все свои цифры, достаточно знать остаток числа при делении на наименьшее общее кратное (НОК) всевозможных цифр (обозначим M), то есть M = 8 * 9 * 5 * 7 = 2520. Стандартная динамика подразумевает следующие параметры состояния: длина уже построенного числа, флаг "строго меньше", текущий остаток по модулю M и маску набора цифр, которые уже встретились.

Первое замечание: можно хранить не маску набора цифр, а, опять же, НОК тех цифр, которые уже вошли в число. Это уменьшит количество возможных значений последнего параметра c 256 до 4 * 3 * 2 * 2 = 48 (4 - кол-во возможных степеней двойки и так далее).

Далее, переходы к новым параметрам при добавлении цифры стоит делать с предподсчетом (от остатка к новому остатку и от НОКа цифр к новому НОКу). Мы хотели и постарались поставить такие ограничения в задаче, чтобы и это решение не проходило (а это было непросто, так как разница между Java и C++ по времени выполнения была разительна; в итоге, к сожалению, часть решений обошла TL без нижеизложенной оптимизации).

Идея, которую хотелось увидеть в динамическом решении — числовая. Если добавлять цифры с конца, то можно заметить, что на остаток числа при делении на 5 влияет лишь последняя цифра. Таким образом, можно хранить флаг "последняя цифра = 5 или 0" и запрещать переходы по цифре 5, если флаг не выставлен. Эта идея уменьшает количество состояний в 5 * 2 / 2 = 5 раз. Такое решение без проблем проходило на любом языке, но есть и более сильные оптимизации, тоже основанные на идее делимости (например, можно провернуть этот же трюк с двойкой).