1. Идея

Нужно посчитать количество двоичных строк длины n, в которых нигде нет подстроки 11.

Главная идея: посмотреть на последнюю позицию строки.

Обозначим через f[n] число допустимых строк длины n.

Тогда любая допустимая строка длины n устроена так:

• либо заканчивается на 0;
• либо заканчивается на 1.

Разберём оба случая:

• Если строка оканчивается на 0, то перед этим может стоять любая допустимая строка длины n - 1. Таких строк f[n - 1].
• Если строка оканчивается на 1, то предыдущий символ обязан быть 0, иначе получится 11. Значит, последние два символа имеют вид 01, а перед ними может стоять любая допустимая строка длины n - 2. Таких строк f[n - 2].

Отсюда получается рекуррентная формула:

f[n] = f[n - 1] + f[n - 2]

Это очень похоже на числа Фибоначчи.

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

Посчитаем первые значения вручную:

• n = 1: строки 0, 1 — всего 2
• n = 2: строки 00, 01, 10 — всего 3
• n = 3: строки 000, 001, 010, 100, 101 — всего 5

Уже видно:

• f[1] = 2
• f[2] = 3
• f[3] = 5

Дальше все значения находятся по формуле:

• f[4] = f[3] + f[2] = 5 + 3 = 8
• f[5] = f[4] + f[3] = 8 + 5 = 13

То есть задача сводится к вычислению последовательности с начальными значениями 2 и 3.

Так как n может быть до 10^6, полный перебор строк невозможен: их всего 2^n, что слишком много.

Но динамика с такой формулой работает очень быстро.

3. Алгоритм

Используем динамику с хранением только двух последних значений.

База

• если n = 1, ответ 2
• если n = 2, ответ 3

Переход

Для i от 3 до n:

• c = (a + b) mod 1000000007
• затем сдвигаем значения:
  • a = b
  • b = c

Здесь:

• a хранит f[i - 2]
• b хранит f[i - 1]
• c станет f[i]

В конце b и будет ответом.

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

Докажем корректность перехода f[n] = f[n - 1] + f[n - 2].

Рассмотрим все допустимые строки длины n.

Случай 1: строка заканчивается на 0

Тогда первые n - 1 символов образуют любую допустимую строку длины n - 1, потому что добавление 0 не создаёт пары 11.

Таких строк ровно f[n - 1].

Случай 2: строка заканчивается на 1

Так как две единицы подряд запрещены, символ перед последней 1 обязан быть 0. Значит, строка оканчивается на 01.

Тогда первые n - 2 символов могут быть любой допустимой строкой длины n - 2.

Таких строк ровно f[n - 2].

Почему случаи не пересекаются

Строка не может одновременно оканчиваться и на 0, и на 1, значит множества строк из двух случаев не пересекаются.

Итого

Общее число допустимых строк:

f[n] = f[n - 1] + f[n - 2]

Базовые случаи:

• f[1] = 2: строки 0, 1
• f[2] = 3: строки 00, 01, 10

Значит, алгоритм последовательно вычисляет правильные значения до f[n], а значит выдаёт верный ответ.

5. Сложность

Цикл выполняется n - 2 раз, каждая операция занимает константное время.

• Время: O(n)
• Память: O(1)

Это хорошо укладывается в ограничения n <= 10^6.

6. Код на C++17

#include <iostream>
using namespace std;

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

    if (n == 1) {
        cout << 2 << '\n';
        return 0;
    }
    if (n == 2) {
        cout << 3 << '\n';
        return 0;
    }

    long long a = 2; // f[1]
    long long b = 3; // f[2]

    for (int i = 3; i <= n; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }

    cout << b % MOD << '\n';
    return 0;
}

7. Код на Python 3

MOD = 1000000007

n = int(input())

if n == 1:
    print(2)
elif n == 2:
    print(3)
else:
    a = 2
    b = 3
    for _ in range(3, n + 1):
        c = (a + b) % MOD
        a = b
        b = c
    print(b)