Для решения задачи, давайте разберем ее по шагам. Мы хотим посчитать количество последовательностей длины N, состоящих из цифр от 0 до K-1, с условием, что никакие два соседних элемента не равны нулю одновременно.

1. **Определим переменные и условия**:

• N - длина последовательности.
• K - максимальная цифра в последовательности (от 0 до K-1).

2. **Разделим последовательности на два типа**:

• Последовательности, заканчивающиеся на 0.
• Последовательности, заканчивающиеся на цифры от 1 до K-1.

3. **Обозначим количество последовательностей**:

• let A[n] - количество последовательностей длины n, заканчивающихся на 0.
• let B[n] - количество последовательностей длины n, заканчивающихся на 1, 2, ..., K-1.
• Общее количество последовательностей длины n: C[n] = A[n] + B[n].

4. **Запишем рекуррентные соотношения**:

• A[n] = B[n-1] (последовательность длины n, заканчивающаяся на 0, может быть получена только из последовательности длины n-1, заканчивающейся на 1, 2, ..., K-1).
• B[n] = (K-1) * C[n-1] (последовательность длины n, заканчивающаяся на 1, 2, ..., K-1, может быть получена из любой последовательности длины n-1, умноженной на (K-1), так как у нас K-1 вариантов для последнего элемента).

5. **Соберем все вместе**:

• Общее количество последовательностей длины n: C[n] = A[n] + B[n].
• Подставим выражения: C[n] = B[n-1] + (K-1) * C[n-1].

6. **Начальные условия**:

• Для n = 1: A[1] = 0 (так как последовательность не может начинаться с 0), B[1] = K-1, C[1] = A[1] + B[1] = K-1.

7. **Реализация алгоритма**:

Теперь мы можем реализовать этот алгоритм в виде кода:

def count_sequences(N, K):
    A = [0] * (N + 1)
    B = [0] * (N + 1)
    C = [0] * (N + 1)

    # Начальные условия
    A[1] = 0
    B[1] = K - 1
    C[1] = A[1] + B[1]

    for n in range(2, N + 1):
        A[n] = B[n - 1]
        B[n] = (K - 1) * C[n - 1]
        C[n] = A[n] + B[n]

    return C[N]

# Пример использования
N = 4  # длина последовательности
K = 5  # максимальная цифра
print(count_sequences(N, K))

8. **Вывод результата**:

После выполнения кода, мы получим количество последовательностей длиной N, удовлетворяющих заданным условиям. Вы можете подставить любые значения N и K в функцию и получить ответ.