Без двух нулей подряд Требуется посчитать количество последовательностей длины n, состоящих из цифр от 0 до k−1 таких, что никакие два соседних элемента последовательности не…

Давайте внимательно разберемся с задачей и подготовим пошаговое решение.

Задача:
Нужно посчитать количество последовательностей длины \( n \), состоящих из цифр от 0 до \( k-1 \), таких что в последовательности не встречаются две подряд идущие нулю.

---

Шаг 1: Понимание ограничения

• Общий набор цифр: от 0 до \( k-1 \).
• Длина последовательности: \( n \).
• Условие: недопустимы последовательности, где есть "00" — два нуля подряд.

---

Шаг 2: Анализ ситуации

Важно понять, что можно выбирать любой элемент на любом шаге, если он не нарушает условие.

Шаг 3: Построение рекуррентной формулы

Обозначим:

• \( a_n \) — количество допустимых последовательностей длины \( n \).

Рассмотрим возможные ситуации для формирования последовательности:

1. Последний элемент — не ноль:

   • Тогда предыдущий элемент может быть как нулём, так и не нулём.
   • Количество таких последовательностей:
     \( (k-1) \times a_{n-1} \), поскольку последний элемент — любой из \( k-1 \) цифр (от 1 до \( k-1 \)).

2. Последний элемент — ноль:

   • Тогда предшествующий элемент не может быть нулём, чтобы не было "00".
   • Значит, предыдущий элемент — любой из \( k-1 \) цифр (0 и остальные, кроме нуля). Но так как последний — ноль, предшественник не должен быть нулём.
   • Количество последовательностей в этом случае: \( a_{n-1}^{(не ноль)} \).

Обозначим:

• \( b_n \) — количество последовательностей длины \( n \), заканчивающихся не нулём.
• \( c_n \) — количество последовательностей длины \( n \), заканчивающихся нулём.

Тогда: \[ a_n = b_n + c_n \]

Выведем рекуррентные формулы:

• Последовательности, заканчивающиеся не нулём: \[ b_n = (k-1) \times a_{n-1} \]
• Последовательности, заканчивающиеся нулём: \[ c_n = b_{n-1} \] (так как чтобы закончить нулём, предыдущий элемент должен быть не ноль).

Итого: \[ a_n = b_n + c_n = (k-1) \times a_{n-1} + b_{n-1} \]

Но зная, что: \[ b_{n-1} = (k-1) \times a_{n-2} \] значит: \[ a_n = (k-1) \times a_{n-1} + (k-1) \times a_{n-2} \]

---

Шаг 4: Начальные условия

• Для \( n=1 \):
  • \( a_1 \): возможны все цифры, то есть \( k \).
  • \( c_1 \): последовательности, заканчивающиеся нулём — всего 1 (последовательность из одного нуля).
  • \( b_1 = a_1 - c_1 = k - 1 \).

Итак: \[ a_1 = k \\ b_1 = k - 1 \\ c_1= 1 \]

Поскольку: \[ a_1 = b_1 + c_1 = (k - 1) + 1 = k \] что совпадает.

---

Шаг 5: Итерационный расчет

Используя полученные формулы:

\[ a_n = (k-1) \times a_{n-1} + (k-1) \times a_{n-2} \] с начальными условиями: \[ a_1 = k, \quad a_2 = (k-1) \times a_{1} + (k-1) \times a_{0} \]

Но что такое \( a_0 \)?

• Для нулевой длины — есть одна "пустая" последовательность: \( a_0=1 \).

---

Итоговая формула:

\[ a_0=1 \\ a_1=k \\ a_n = (k-1) \times (a_{n-1} + a_{n-2}) \]

Итоговая программа на Python:

k = int(input())  # число вариантов цифр
n = int(input())  # длина последовательности

# Начальные условия
a_prev_prev = 1  # a_0
a_prev = k     # a_1

for i in range(2, n + 1):
    a_curr = (k - 1) * (a_prev + a_prev_prev)
    a_prev_prev, a_prev = a_prev, a_curr

print(a_prev)

---

Итог:

Вывод программы — количество таких последовательностей, при условии, что:

• длина — \( n \),
• набор цифр — 0, 1, ..., \( k-1 \),
• и запрещены последовательности с двумя нулями подряд.

---

Если нужно, я могу помочь с разбором тестовых примеров или дополнительно объяснить шаги!