Числа с заданным свойством

Облегчение

Решим сначала задачу найти количество чисел \< $10^k$ с суммой $S$, пусть dp[i][j] - количество чисел из i разрядов с суммой j, тогда ответ - dp[k][s], формула пересчета же следующая $dp[i + 1][j + c] += dp[i][j] \forall c in [0, 9]$

Возвращение

Заметим, что единственное, что теперь меняется, это то что нам нужно знать меньше ли то число которое мы набрали нашего $k$ или нет, давайте, тогда изменим нашу динамику на $dp\[i\]\[s\]\[can\]$ - мы набрали первые i цифр числа, с суммой s и при этом can = 1, если мы уже меньше числа $k$ и 0 иначе, тогда база - dp[0][0][0] = 1, пусть $k_{i}$ - i-ая цифра с начала числа $k$, формула перехода $dp[i][j][0] = \sum\limits_{c = 0}^{c \<= k_{i - 1}} dp[i - 1][j - c][0], dp[i][j][1] = \sum\limits_{c = 0}^{c \< k_{i - 1}} dp[i - 1][j - c][0] + \sum\limits_{c = 0}^{c \<= 9} dp[i - 1][j - c][1]$, ответ - dp[len(k)][s][1] + dp[len(k)][s][0].

---

Задача

Найти количество чисел из $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}$

Также можно подумать о комбинаторном решении задачи.