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

Длина слова n = 5. Алфавит в порядке возрастания: А, Г, И, Л, М, О, Р, Т. Всего букв b = 8; повторения букв разрешены.

Сопоставим буквам цифры от 0 до b − 1: А → 0, Г → 1, И → 2, Л → 3, М → 4, О → 5, Р → 6, Т → 7. Алфавитное сравнение слов одинаковой длины совпадает со сравнением позиционных записей: решает первая различающаяся буква слева. Начальные нули сохраняем, поскольку длина слова фиксирована.

Номер в списке на единицу больше значения записи. Для цифр d₁, …, dₙ формула имеет вид N = 1 + d₁ · bⁿ⁻¹ + d₂ · bⁿ⁻² + … + dₙ. Единица нужна потому, что первое слово состоит из минимальных букв, его код равен нулю, а номер равен 1.

Условия отбора: первая буква не входит в Л; число букв И от 2 до 5 включительно; номер чётный.

Основание b чётное: все позиционные слагаемые, кроме последнего, чётные. Поэтому чётность N определяется числом 1 + dₙ.

Считаем слова отдельно для каждой первой буквы и каждого числа k букв И, где k = 2, 3, 4, 5. Обозначим Dᵢ(k, r) число заполнений первых i мест, содержащих k нужных букв и имеющих остаток r позиционного значения при делении на 2. Для фиксированной первой буквы начальное значение равно 1 в состоянии, заданном её кодом и весом 8⁴; остальные состояния равны нулю.

Переход: пробуем очередную букву с кодом d. Если она совпадает с искомой, увеличиваем k на 1. Новый остаток равен остатку от r + d · bⁿ⁻ⁱ при делении на 2. Прибавляем число способов старого состояния к новому. После n мест оставляем нужные k и остаток для чётного N: он равен 1, поскольку N = 1 + значение записи. Запрет первой буквы обнуляет всю соответствующую строку.

Итоговые числа по k в указанном порядке:
Первая А: 84, 4, 0, 0; сумма = 88.
Первая Г: 84, 4, 0, 0; сумма = 88.
Первая И: 588, 84, 4, 0; сумма = 676.
Первая Л: 0, 0, 0, 0; сумма = 0.
Первая М: 84, 4, 0, 0; сумма = 88.
Первая О: 84, 4, 0, 0; сумма = 88.
Первая Р: 84, 4, 0, 0; сумма = 88.
Первая Т: 84, 4, 0, 0; сумма = 88.

Всего слов = 88 + 88 + 676 + 0 + 88 + 88 + 88 + 88 = 1204.

Проверка: полный перебор всех 8⁵ = 32768 слов с нумерацией от 1 и непосредственной проверкой каждого ограничения даёт 1204. Здесь нужен именно размер отобранного множества: номера исходного списка не перенумеровываются после фильтрации.

Ответ: 1204.