Задача g6_1025: Домино (#Z001)

Задание. Написать программу DOMINO.*, подсчитывающую количество вариантов покрытия прямоугольника 2хN прямоугольниками 2х1. Покрытия, которые преобразуются одно в другое симметриями, считать различными.
Входные данные. Входной файл DOMINO.DAT содержит число N (0 < N < 65536).

Выходные данные. Выходной файл DOMINO.SOL должен содержать одно число: количество вариантов.

Примеры ввода и вывода

DOMINO.DAT : 1
DOMINO.SOL : 1

Решение g6_1025:
Очередная задача, раньше числившаяся в разряде нерешенных.
Попробуем нарисовать все возможные комбинации на листе бумаги и записать количество возможных вариантов:

0 :: 1
1 :: 1
2 :: 2
3 :: 3
4 :: 5
5 :: 8
6 :: 13

Уфф... уморился. Ну ладно, этого нам вполне достаточно, чтобы предположить, что количество вариантов расположения n костяшек домино равно n-му члену последовательности чисел Фибоначчи. Для тех, кто не знает расскажу, а для тех, кто знает напомню, что каждое число Фибоначчи (за исключением первых двух членов) представляется как сумма двух предыдущих.
В этой задаче такое предположение легко доказывается:
Если мы имеем последовательность из n костяшек, то мы можем получить последовательность из n+1 костяшек прибавлением одной вертикальной костяшки. Также последовательность из n+1 костяшки можно получить прибавлением двух горизонтальных костяшек к последовательности из n-1 костяшки. Других вариантов нет (нарисуйте, и разберитесь почему) - они будут повторяться с одной из приведенных выше комбинаций.

Теперь перед нами стоит задача посчитать числа Фибоначчи до 65536 члена. Сразу замечу, что я написал программу, которая считает 65536 член Фибоначчи примерно за 30 секунд на 400-ом Селероне. Если кто-нибудь напишет быстрее, присылайте - буду очень благодарен!
Для подсчета больших чисел Фибоначчи нам понадобится длинная арифметика, причем очень длинная - около 15000 десятичных знаков. Заведем три массива длиной 20000(на всякий случай), состоящих из элементов byte. Один из массивов будет равен F(n-2), другой F(n-1), третий F(n). Первоначально инициализируем последние элементы массивов F(n-2) и F(n-1) соответственно 1 и 2. Для ускорения сложения заведем переменную, указывающую на первую цифру наибольшего числа. Первоначально эта переменная содержит 20000 (цифра одна).
Теперь перейдем к написанию процедуры сложения двух длинных чисел. Для этого нам надо идти с конца массива до указателя на первую цифру(в дальнейшем k), изменяя значение переменной c от 20000 до k.

F(n)[c] := F(n-2)[c] + F(n-1)[c] + flag;
flag := F(n)[c] div 10;
F(n)[c] := F(n)[c] mod 10;

Сложение напоминает сложение столбиком, где переменная flag - это число "в уме"(первоначально равно нулю). После сложения стоит производить такие действия:

for c := k to 20000 do begin
F(n-2)[c] := F(n-1)[c];
F(n-1)[c] := F(n)[c];
end;

Мы записываем в F(n-2) число F(n-1), а в число F(n-1) - число F(n), т.е. увеличиваем n на 1.
В конце нам следует вывести все элементы массива F(n) от k да 20000 - это и будет искомым числом!