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

Длина слова n = 6. Алфавит в порядке возрастания: А, Ж, И, М, Н, У, Ч. Всего букв b = 7; повторения букв разрешены.

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

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

Условия отбора: первая буква не входит в Ж; число букв Ч от 0 до 1 включительно; номер чётный.

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

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

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

Итоговые числа по k в указанном порядке:
Первая А: 3888, 3240; сумма = 7128.
Первая Ж: 0, 0; сумма = 0.
Первая И: 3888, 3240; сумма = 7128.
Первая М: 3888, 3240; сумма = 7128.
Первая Н: 3888, 3240; сумма = 7128.
Первая У: 3888, 3240; сумма = 7128.
Первая Ч: 0, 3888; сумма = 3888.

Всего слов = 7128 + 0 + 7128 + 7128 + 7128 + 7128 + 3888 = 39528.

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

Ответ: 39528.