Как найти количество последовательностей 0, 1 и 2 и длины n, в которых нет k последовательных одинаковых чисел? ⇐ C++

[Anonymous]

Мне нужно написать программу на C++, которая вводит n и k и выводит, сколько существует последовательностей 0, 1 и 2 длиной n без k последовательных равных чисел. N и k достигают миллиона, поэтому мне нужно решение O(n) или O(k).
Я сделал это для k=2, где ответ 3*2^( n-1), но я не могу придумать решение для k>2.

Подробнее здесь: https://stackoverflow.com/questions/792 ... hat-dont-h