Последовательности из 0, 1 и 2 без двух единиц и двоек подряд

Кем гарантируется, что ответ не превосходит 32-битного максимума? Это может быть гарантировано только для n < какой-то величины, а не какими-то голословными утверждениями в постановке.

Соотношения:

 F(n, x) - кол-во последовательностей, начинающихся на цифру x (или оканчивающихся, неважно)

F(n) = F(n, 0) + F(n, 1) + F(n, 2)



F(1, 0) = F(1, 1) = F(1, 2) = 1

F(1) = 3

F(2) = 7

F(3) = 17

F(n, 0) = F(n-1, 0) + F(n-1, 1) + F(n-1, 2)

F(n, 1) = F(n-1, 0) + F(n-1, 2)

F(n, 2) = F(n-1, 0) + F(n-1, 1)



F(n) = F(n, 0) + F(n, 1) + F(n, 2) = 3 ∙ F(n-1, 0) + 2 ∙ F(n-1, 1) + 2 ∙ F(n-1, 2) =

  = 3 ∙ F(n-1) - F(n-1, 1) - F(n-1, 2) = 3 ∙ F(n-1) - F(n-2) - F(n-2, 0) =

  = 3 ∙ F(n-1) - F(n-2) - F(n-3) 

Таким образом, мы можем избежать вычислений экспоненциальной сложности (попробуйте в вышеприведённой программе ввести 40 - поймёте, о чём я говорю). И конечно, никакая рекурсия здесь 100 лет не нужна, вычисляем значения снизу вверх и используем 3 последних в следующих вычислениях.

 #include 



using namespace std;



int main() {

    unsigned n;

    cin >> n;

    unsigned long long comb[4] = { 0, 3, 7, 17 };

    for (; n > 2; n--) {

        comb[0] = comb[1];

        comb[1] = comb[2];

        comb[2] = comb[3];

        comb[3] = 3 * comb[2] - comb[1] - comb[0];

    }

    cout

обозначим F(n, x) - количество последовательностей длины n, оканчивающихся на цифру x

получаем рекуррентные соотношения:
F(1, 0) = F(1, 1) = F(1, 2) = 1
F(n, 0) = F(n-1, 0) + F(n-1, 1) + F(n-1, 2)
F(n, 1) = F(n-1, 0) + F(n-1, 2)
F(n, 2) = F(n-1, 0) + F(n-1, 1)

и требуется вывести:
F(n, 0) + F(n, 1) + F(n, 2)

 #include



unsigned int f (int n, char x) {

    if (n == 1) return 1;

    if (x == 1) return f(n-1, 0) + f(n-1, 2);

    if (x == 2) return f(n-1, 0) + f(n-1, 1);

    return f(n-1, 0) + f(n-1, 1) + f(n-1, 2);

}



using namespace std;



int main() {

    int n;

    cin >> n;

    cout