Задача 39: K-ичные числа (acm.timus.ru)
Требуется вычислить количество N-значных чисел в системе счисления с
основанием K, таких, что их запись не содержит двух подряд идущих
нулей.
Ограничения: 2 <= K <= 10; 1 <= N+K <= 18.
Входные данные.
Во входном файле INPUT.TXT содержатся числа N и K в десятичной
записи, разделенные пробелом или переводом строки.
Вывод.
Программа должна выдать в файл OUTPUT.TXT искомое число в
десятичной записи.
Пример входного файла:
2
10
Пример выходного файла:
90
Решение:
Эта задача на acm.timus.ru
предлагается в 3 вариантах. В первом ограничение N+K <= 18, во
втором 180, а в третьем 1800. Здесь будет изложено решение первого
варианта этой задачи, т.к. главное здесь это понять метод решения, а
сделать длинную арифметику несложно.
Для первого варианта в принципе возможен полный перебор, но
существование 2 других задач, с такими жесткими условиями, говорит
нам о том, что здесь его применять нельзя. Придется подумать... что,
в общем-то, нам не свойственно...
Вспомним задачу Принцип компании. Если там представить газету
как 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)
Ну а числа Фибоначчи мы искали уже много раз, например в задаче
Домино
Далее
ð
