Задача g6_1061: K-ичные числа (acm.timus.ru)

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких, что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10; 1 <= N+K <= 18.

Входные данные.
Во входном файле INPUT.TXT содержатся числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Вывод.
Программа должна выдать в файл OUTPUT.TXT искомое число в десятичной записи.
Пример входного файла:
2
10
Пример выходного файла:
90

Решение g6_1061:
Эта задача на acm.timus.ru предлагается в 3 вариантах. В первом ограничение N+K <= 18, во втором 180, а в третьем 1800. Здесь будет изложено решение первого варианта этой задачи, т.к. главное здесь это понять метод решения, а сделать длинную арифметику несложно.
Для первого варианта в принципе возможен полный перебор, но существование 2 других задач, с такими жесткими условиями, говорит нам о том, что здесь его применять нельзя. Придется подумать... что, в общем-то, нам не свойственно...
Вспомним задачу #1043 Принцип компании. Если там представить газету как 1, а буклет как 0, то получим решение нашей задачи для частного случая, когда K = 2. Попробуем применить этот метод для произвольного K.
Последовательность из 0 элементов у нас одна. Из одного элемента - K. А вот над последовательностями из двух и более элементов придется призадуматься.
Мы получим корректную последовательность длиной t если к корректной последовательности длиной t - 1 допишем любую из K - 1 цифры (кроме нуля). Т.е.:
0, 1, 2 - последовательность из 1 элемента.
Для них корректны последовательности из двух элементов:
01, 02, 11, 12, 21, 22
Однако мы не учли, что последней цифрой может быть 0, но для этого необходимо, чтобы t-1 цифра не была нулем. Как же этого добиться?
Взглянем, что у нас получилось. У нас получились последовательности длиной t, у которых последняя цифра - не ноль. Их количество равно количеству последовательностей из t-1 элемента [f(t-1)] умножить на k-1.
Получается:
f(t) = (k-1)*f(t-1) + (k-1)*f(t-2)
К любой последовательности длины n-1 мы можем дописать любую из k-1 ненулевых цифр, отсюда (k-1)*f(t-1). К любой последовательности длины n-2 мы можем дописать любую ненулевую цифру и ноль, т.е. (k-1)*f(t-1)
Ну а числа Фибоначчи мы искали уже много раз, например в задаче #1025 Домино