Найти количество способов составить строку из символов A и B длины n, в которой нет трех подряд идущих символов B и четырех подряд идущих символов А

Question

Длина строки n больше 0, но не больше 1000. Нужно найти количество способов составить строку длины n, где нет трёх идущих подряд В и четырёх идущих подряд А. Вывести нужно количество способ делённое на (10^9 + 7). Пробовал решить рекурсией, но если n 30 и больше, то уже очень долго решает. Других идей нет. Как можно решить эту задачу эффективно?

Вот код на C++:

#include <iostream>
using namespace std;

int i, n, spos;
long int del;
int temp;

void Count(int len, string b)
{
    if (len < n)
    {
        if (b == "B" || b == "BB")
        {
            Count(len + 1, "A");
            Count(len + 2, "AA");
            Count(len + 3, "AAA");
        }
        else if (b == "A" || b == "AA" || b == "AAA")
        {
            Count(len + 1, "B");
            Count(len + 2, "BB");
        }
    }
    else if (len == n)
    {
        spos += 1;
    }
}

int main()
{
    cin >> n;
    Count(1, "B");
    Count(2, "BB");
    Count(1, "A");
    Count(2, "AA");
    Count(3, "AAA");
    del = pow(10, 9) + 7;
    cout << spos % del;
}

Answer 1

Эту задачу можно решить с помощью динамического программирования вместо рекурсии. Заводите массив размером 5x1000, где пять столбцов относятся к комбинациям, которые вы уже перечислили. Инициализируете:

M[0][0] = 1;
M[0][1] = 0;
M[0][2] = 1;
M[0][3] = 0;
M[0][4] = 0;

Затем в цикле:

M[i][0] = (M[i-1][2] + M[i-1][3] + M[i-1][4]) % modulo;  //'B'
M[i][1] = M[i-1][0];                                    //'BB'
M[i][2] = (M[i-1][0] + M[i-1][1]) % modulo;            //'A'
M[i][3] = M[i-1][2];                                  //'AA'
M[i][4] = M[i-1][3];                                 //'AAA'

И результат - сумма последней заполненной строки

В общем-то, такой длинный массив не нужен, можно обойтись двумя строками, заполняя то нулевую, то первую

M[i&1][1] = M[(i+1)&1][0];

Для ограничения в 1000 этого хватит. Если же придётся считать для очень больших длин, то можно использовать матричный способ
(как это работает - можно посмотреть для матричного вычисления больших чисел Фибоначчи)

[Mn0]    [ 0 0 1 1 1 ]^(n-1)       [1]
[Mn1]    [ 1 0 0 0 0 ]             [0]
[Mn2] =  [ 1 1 0 0 0 ]        *    [1] 
[Mn3]    [ 0 0 1 0 0 ]             [0] 
[Mn4]    [ 0 0 0 1 0 ]             [0]

(возможно, матрицу надо транспонировать)

а возведение матрицы в степень выполняется за log(n) операций умножения матриц с помощью быстрого алгоритма (бинарное возведение в степень, пример для чисел), причем внутри умножений надо не забывать про взятие модуля.

Answer 2

Не удержался и набросал в олимпиадном стиле:

#include <iostream>

int main() {
    unsigned mod = 1000000007;
    unsigned a = 1, aa = 0, aaa = 0, b = 1, bb = 0;

    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        auto ta = (b + bb) % mod;
        auto tb = (a + aa + aaa) % mod;
        aaa = aa;
        aa = a;
        bb = b;
        a = ta;
        b = tb;
    }
    std::cout << (a + b) % mod << '\n';
}

БЛОГ НА HUSL

Найти количество способов составить строку из символов A и B длины n, в которой нет трех подряд идущих символов B и четырех подряд идущих символов А

Ответы (2 шт):