1. Идея

Нужно посчитать количество способов добраться из позиции 0 до камня n, если за один прыжок можно перейти на 1 или 2 позиции вперёд, а на сломанные камни вставать нельзя.

Это типичная задача на динамическое программирование.

Будем считать dp[i] — количество способов попасть на позицию i.

Тогда:

• если камень i сломан, то dp[i] = 0;
• иначе на него можно прийти:
  • с позиции i - 1,
  • с позиции i - 2.

Значит, для целого камня:

• dp[i] = dp[i - 1] + dp[i - 2].

Так как нужен ответ по модулю 1000000007, все вычисления делаем по модулю.

2. Наблюдения

Наблюдение 1

Берег — это позиция 0, и в начале лягушка уже находится там.
Значит:

• dp[0] = 1.

Это означает: есть ровно один способ быть на берегу — просто стартовать там.

Наблюдение 2

Если камень сломан, на него приземляться нельзя, поэтому:

• dp[i] = 0, если b[i] = 1.

Наблюдение 3

Для целого камня i:

• если i = 1, то на него можно попасть только из 0, поэтому dp[1] = dp[0], если камень не сломан;
• если i >= 2, то:
  • с i - 1,
  • с i - 2, поэтому dp[i] = dp[i - 1] + dp[i - 2].

Наблюдение 4

Для вычисления очередного значения нужны только два предыдущих.
Значит, не обязательно хранить весь массив dp, достаточно двух переменных:

• значение для i - 2,
• значение для i - 1.

Именно так и сделано в эталонном решении.

3. Алгоритм

Будем идти по камням слева направо и поддерживать:

• dp_im2 — значение dp[i - 2],
• dp_im1 — значение dp[i - 1].

Начальные значения подбираем так, чтобы единая формула cur = dp_im1 + dp_im2 работала уже для i = 1:

• dp_im1 = dp[0] = 1 — единственный способ стоять на берегу;
• dp_im2 = dp[-1] = 0 — несуществующая позиция, способов нет.

Тогда для i = 1 получится cur = dp_im1 + dp_im2 = 1 + 0 = 1 = dp[1], а для i >= 2 формула даёт dp[i] = dp[i - 1] + dp[i - 2].

Далее для каждого i от 1 до n:

1. Если b[i] = 1, то текущий камень сломан:

   • cur = 0.

2. Иначе камень целый:

   • cur = (dp_im1 + dp_im2) % MOD.

3. После этого сдвигаем значения:

   • dp_im2 = dp_im1
   • dp_im1 = cur

В конце:

• dp_im1 — это dp[n], его и выводим.

4. Почему это работает

Докажем, что алгоритм действительно считает количество способов попасть на каждый камень.

Рассмотрим произвольный камень i.

Случай 1: камень i сломан

По условию на него нельзя приземляться.
Значит, способов попасть на него нет, то есть dp[i] = 0.

Алгоритм именно это и делает: если b[i] = 1, он присваивает cur = 0.

Случай 2: камень i целый

Лягушка умеет прыгать только на 1 или на 2 позиции вперёд.
Значит, последний прыжок на i мог быть только:

• с i - 1,
• с i - 2.

Других вариантов нет.

Тогда общее число способов попасть на i равно сумме:

• числа способов попасть на i - 1,
• числа способов попасть на i - 2.

То есть:

• dp[i] = dp[i - 1] + dp[i - 2].

Если i = 1, то позиция i - 2 = -1 не существует. Мы заводим для неё фиктивное значение dp[-1] = 0, поэтому общая формула остаётся верной:

• dp[1] = dp[0] + dp[-1] = 1 + 0 = 1, если камень не сломан.

Алгоритм ровно это и реализует благодаря начальным значениям dp_im1 = 1, dp_im2 = 0.

Почему достаточно двух переменных

Формула для dp[i] использует только dp[i - 1] и dp[i - 2].
Значит, после вычисления очередного значения более старые уже не нужны.

Поэтому можно хранить только два последних значения и на каждом шаге обновлять их.
Это не меняет результат, но уменьшает расход памяти.

Следовательно, после обработки всех камней dp_im1 будет равно dp[n], то есть количеству способов добраться до камня n.

5. Сложность

Пусть n — число камней.

• Время работы: O(n), потому что каждый камень обрабатывается один раз.
• Дополнительная память: O(1), если не считать массив входных данных.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    int n;
    cin >> n;

    vector<int> b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    long long dp_im2 = 0; // dp[-1]
    long long dp_im1 = 1; // dp[0]

    for (int i = 1; i <= n; i++) {
        long long cur;
        if (b[i] == 1) {
            cur = 0;
        } else {
            cur = (dp_im1 + dp_im2) % MOD;
        }
        dp_im2 = dp_im1;
        dp_im1 = cur;
    }

    cout << dp_im1 << "\n";
    return 0;
}

7. Код на Python 3

MOD = 1000000007

n = int(input())
b = [0] + list(map(int, input().split()))

dp_im2 = 0
dp_im1 = 1

for i in range(1, n + 1):
    if b[i] == 1:
        cur = 0
    else:
        cur = (dp_im1 + dp_im2) % MOD
    dp_im2 = dp_im1
    dp_im1 = cur

print(dp_im1)