Задание EGEINF921F48: Подсчёт слов и последовательностей

Основание системы 9, число разрядов 5. Цифра 3 должна встретиться от 0 до 1 раз включительно. Ведущий ноль исключаем. Разрешённые цифры первого места: 2, 4, 6, 8; последнего: 0, 2, 3, 4, 5, 6, 7. На промежуточных местах разрешены все цифры от 0 до 8.

Пусть Fᵢ(k) — число способов заполнить первые i мест так, чтобы цифра 3 встретилась ровно k раз. До заполнения F₀(0) = 1, остальные значения нулевые. Для очередного места обозначим через a число разрешённых обычных цифр, через z — возможность поставить особую цифру (0 или 1).

Общая формула перехода: Fᵢ(k) = a · Fᵢ₋₁(k) + z · Fᵢ₋₁(k − 1). Первое слагаемое добавляет обычную цифру, второе добавляет особую и увеличивает её количество на один. Для отрицательных k принимаем значение ноль. Случаи не пересекаются и охватывают все способы заполнить очередное место.

В строке i указаны значения Fᵢ(0), …, Fᵢ(i):
i = 1: a = 4, z = 0; значения 4, 0.
i = 2: a = 8, z = 1; значения 32, 4, 0.
i = 3: a = 8, z = 1; значения 256, 64, 4, 0.
i = 4: a = 8, z = 1; значения 2048, 768, 96, 4, 0.
i = 5: a = 6, z = 1; значения 12288, 6656, 1344, 120, 4, 0.

Суммируем разрешённые количества особой цифры: 12288 + 6656 = 18944.

Проверка: сумма всей последней строки равна 20412 = 4 · 9 · 9 · 9 · 7, то есть числу всех записей с допустимыми крайними цифрами. Независимый прямой перебор с ограничением на количество цифр 3 даёт 18944. Числа с ведущим нулём в расчёт не попадают.

Ответ: 18944.