Количество чисел у которых две соседние цифры различной четности
Материал из Algocode wiki
Версия от 12:00, 27 апреля 2020; Глеб (обсуждение | вклад) (Новая страница: «==Задача== Найти количество чисел из $n$ разрядов, у которых все соседние цифры разной четн...»)
Задача
Найти количество чисел из $n$ разрядов, у которых все соседние цифры разной четности
Решение
1) $dp_{i, mod}$ - количество чисел из $i$ разрядов с четностью последней цифры - mod 2) База $dp_{1, 1} = 4, dp_{1, 0} = 1$ 3) $dp_{i, mod} = dp_{i - 1, 1 \bigoplus mod} \cdot 5$ 4) Порядок обхода - вперед 5) Ответ - $dp_{n, 0} + dp_{n, 1}$
Также можно подумать о комбинаторном решении задачи.