Для нахождения D(N-K) в формуле (1) будем использовать процедуры длинной арифметики. Каждое длинное число представим последовательностью байтов, содержащих его десятичные цифры от младших разрядов к старшим. Потребуются такие процедуры как преобразование короткого числа типа INTEGER в длинное, сложение длинных чисел, умножение короткого числа на длинное и т. п.

Для сокращения числителя и знаменателя представим знаменатель как массив сомножителей с кратностью каждого из них не более 2. Найденный числитель будем пытаться поделить нацело на каждый из сомножителей в порядке убывания их величины с учетом кратности сомножителей. Для этого потребуется процедура деления длинного числа на короткое.

Наконец, на заключительном этапе нужно найти произведение тех сомножителей знаменателя, которые не были сокращены.

По заданным ограничениям все числа не превосходят 100¹⁰⁰, поэтому для представления любого длинного числа потребуется не более 200 байтов.

Приведем текст программы. Процедуры и функции длинной арифметики используются без изменений, поэтому в тексте содержатся только их заголовки.

Program Mag;

Const

numlen = 200; {число разрядов длинного числа - с запасом}

Label

Konec;

Type

number=array[1..numlen] of byte;

Var

M,N,K,L,i,j,jj : integer;

Min,Max: integer;

d1,d2,d3: number;

Num: array[1..100] of integer;

{кратность сомножителей знаменателя}

Fin,Fout: text;

Procedure Set0(var n:number); {обнуление длинного числа}

Procedure SetN(Var n: number; short: integer);

{занесение короткого числа в длинное}

Function Len(var n:number): integer;

{получение длины числа, для нуля длина 1}

Procedure Show(var n:number);

{вывод числа в файл Fout}

Procedure MulShort(Var n: number; short: integer);

{умножение длинного числа на короткое}

Procedure DivShort(Var n: number; divisor: integer;

Var rem: integer);

{деление длинного числа на короткое и получение остатка}

Procedure Add(Var n1,n2: number);

{сложение длинных чисел}

Procedure Move(n1:number; Var n2:number);

{пересылка длинного числа - n2:=n1}

Begin {основная программа}

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,K,N);

Close(Fin);

Set0(d1); { d1:=0 }

SetN(d2,1); { d2:=1 }

L:=N-K;

Assign(Fout,'output.txt');

Rewrite(Fout);

if L=1 then

begin

WriteLn(Fout,'0');

Goto Konec;

end;

{нахождение числителя d3}

if (L=0) or (L=2) then SetN(d3,1); { d3:=1 }

For i:=3 to L do

begin

Add(d1,d2); { d1:=d1+d2 }

Move(d1,d3); { d3:=d1 }

MulShort(d3,i-1);

Move(d2,d1); { d1:=d2 }

Move(d3,d2); { d2:=d3 - следующий шаг }

end;

if L<K then

begin

Min:=L;

Max:=K;

end

else

begin

Min:=K;

Max:=L;

end;

For i:=1 to Min do Num[i]:=2;

{кратность сомножителей знаменателя,

в K! и (N-K)! начальные сомножители повторяются}

For i:=Min+1 to Max do Num[i]:=1;

For i:=Max downto 2 do {проверка: можно ли сократить на i}

begin

jj:=Num[i]; {сомножитель i в знаменателе N[i] раз}

For j:=1 to jj do

begin

Move(d3,d1); {d1:=d3}

DivShort(d1,i,M); {M-остаток}

if M=0 then

begin

Num[i]:=Num[i]-1;

Move(d1,d3); {сокращение на i}

end

else break; {нет сокращения - выход из цикла по j}

end;

end;

SetN(d2,1);

{нахождение знаменателя d2 после сокращения}

For i:=2 to Max do

For j:=1 to Num[i] do

MulShort(d2,i);

Show(d3); {вывод в файл d3}

Write(Fout,'/');

Show(d2);

Konec:

Close(Fout);

End.

Необходимые для решения задачи процедуры и функции длинной арифметики используются без какого-либо изменения и настройки. В качестве упражнений можно порекомендовать довести до конца при максимальных размерностях решение приведенных выше задач, которые требуют применения длинной арифметики. Полезно также переработать процедуры длинной арифметики на язык Си и протестировать их на небольших комбинаторных задачах.

3. Рекуррентные соотношения

Рассмотрим следующую задачу. Имеются последовательности длины N, состоящие из 0 и 1. Требуется по заданному числу N (1 £ N £ 40) определить количество таких последовательностей, в которых никакие две единицы не стоят рядом.

Казалось бы, задача очевидна. При заданном N имеется 2^N последовательностей из нулей и единиц. Действительно, в каждой позиции может находиться два значения, а отдельные разряды независимы. Можно перечислять последовательности и проверять с помощью стандартных функций, имеются ли две единицы рядом. Останется из 2^N последовательностей вычесть число последовательностей с двумя единицами подряд.

Снова обратим внимание на размерность. При N=30 значение 2^N превышает миллиард. А если N еще больше?

Рассмотрим другой подход к решению задачи. Обозначим через F(N) количество последовательностей с заданным свойством. Возможны два случая:

• на месте N стоит 0;

• на месте N стоит 1.

В первом случае в позициях от 1 до N-1 может находиться любая последовательность без двух единиц рядом, то есть общее число последовательностей составляет F(N-1).

Во втором случае на месте N-1 обязан находиться 0, иначе последовательность закончится двумя единицами подряд. А вот в позициях от 1 до N-2 может находиться любая последовательность без двух единиц рядом. Таким образом, общее число искомых последовательностей составляет F(N-2).

В результате получаем формулу F(N)=F(N-1)+F(N-2), совпадающую с правилом вычисления чисел Фибоначчи. Значение функции F на любом шаге определяется через ее значения на предыдущих шагах. Такие формулы называются рекуррентными.

Легко установить, что F(1)=2, F(2)=3. Поэтому F(3)=F(2)+F(1)=5, F(4)=F(3)+F(2)=8, F(5)=F(4)+F(3)=13 и т. д.

Сейчас вычислений немного, но есть другая трудность. Последовательность Фибоначчи быстро растет, а результатом должно быть целое число, которое при больших N невозможно представить точно стандартными целочисленными типами данных. В таких случаях используют собственные типы данных и процедуры работы с ними. Их в совокупности называют длинной арифметикой. Мы рассмотрим эти проблемы ниже.

Сформулируем еще одну похожую задачу.

Сообщение. В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Ввод из файла INPUT.TXT. В первой строке содержится последовательность цифр.

Вывод в файл OUTPUT.TXT. Вывести одно число.

Ограничения: цифр не более 100, время 1 с.

Пример

Ввод

1025

Вывод

4

Обозначим через F(N) количество сообщений, которые можно сформировать из первых N цифр. Попытаемся выразить F(N+1) через значения этой функции на предыдущих шагах. Рассмотрим два случая:

• цифры на местах N и N+1 образуют двухзначное число, большее 33;

• цифры на местах N и N+1 образуют двухзначное число, не превышающее 33.

В первом случае любое сообщение, зашифрованное первыми N цифрами, может быть дополнено буквой, код которой содержится в позиции N+1. В то же время последние две цифры не могут кодировать какую-либо букву. Значит, в этом случае F(N+1)=F(N).

Во втором случае помимо этого любое сообщение, представленное первыми N-1 цифрами, может быть дополнено буквой, код которой содержится в позициях N и N+1. В этом случае F(N+1)= F(N)+ F(N-1).

Очевидно, F(1)=1. Правильно считать, что F(0)=1 – пустое сообщение, которое может дополняться. Далее проблем не видно. Снова потребуется использование длинной арифметики.

Задачи для самостоятельного решения

3.1. Заяц (5)

Имеется лестница, состоящая из N ступенек. При подъеме по лестнице заяц может прыгать на любое количество ступенек от 1 до K. Сколько у зайца способов подъема по лестнице?

Ввод из файла INPUT.TXT. Единственная строка содержит целые положительные числа N и K.

Вывод в файл OUTPUT.TXT. Выводится единственное число - количество способов подъема по лестнице.

Ограничения: 1 ≤ K, N ≤ 35, время 1 с.

Пример

Ввод

3 2

Вывод

3

3.2. Что в имени твоем? (6)

В алфавите племени мумба-юмба только три буквы, которые обозначаются как A, B и D. Юношам в день совершеннолетия принято давать взрослые имена, состоящие ровно из N букв. Повторение букв в имени не ограничивается. Если юноша не может представить вождю скальп врага, то в имени присутствует подстрока BAD (возможно, в нескольких экземплярах), иначе такие имена категорически запрещаются. Сколько разных имен может быть в племени мумба-юмба для юношей, запоздавших в развитии (не представивших скальп)?

Ввод из файла input.txt. Единственная строка содержит целое положительное число N.

Вывод в файл OUTPUT.TXT. Выводится единственное число - количество имен длины N, содержащих подстроку BAD.

Ограничения: 1 ≤ N ≤ 35, время 1 с.

Пример

Ввод

8

Вывод

1404

3.3. Числа (6)

Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких, что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

Чтобы ответить на поставленный вопрос, Вова решил написать программу, которая позволит ему найти число различных последовательностей неотрицательных целых чисел, в каждой из которых любое число не превосходит C. Он понимал, что такое число могло быть достаточно большим, поэтому ограничился поиском только последних k цифр этого числа.

Написать программу, которая покажет Вове, как можно правильно решить поставленную им задачу.

Ввод из файла INPUT.TXT. Первая строка входного файла содержит три целых числа — n, C и k (1 ≤ n ≤ 50000, 1 ≤ C ≤ 10⁸, 1 ≤ k ≤ 18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

Вывод в файл OUTPUT.TXT. Выводится последние k цифр искомого количества последовательностей без ведущих нулей.

Примеры

Ввод 1 Ввод 2 Ввод 3

3 11 2 1 8 3 10 9 1

111 9 0123456789876543210

Вывод 1 Вывод 2 Вывод 3

3 0 0

3.4. K-ичные числа (6)

Найти количество натуральных N-значных (1 ≤ N ≤ 20) чисел в системе счисления с основанием K (2 ≤ K ≤ 8), таких, что их запись не содержит двух подряд идущих нулей.

Ввод из файла INPUT.TXT. В единственной строке содержатся числа N и K в десятичной записи, разделенные пробелом.

Вывод в файл OUTPUT.TXT. Программа должна выдать искомое число в десятичной записи.

Пример

Ввод

2 4

Вывод

12

3.5. Распил бруса (7)

На пилораму привезли брус длиной L метров. Известны места, в которых необходимо сделать распилы. Стоимость одного распила равна длине распиливаемого бруса. Различный порядок распилов приводит к различным итоговым ценам. Например, брус длиной 10 метров, который нужно распилить на расстоянии 2, 4 и 7 метров можно пилить разными способами. Можно распилить сначала на отметке 2, потом 4 и потом 7. Стоимость будет 10+8+6=24. А если сначала распилить на отметке 4, потом 2 и затем 7, то стоимость составит 10+4+6=20. Требуется написать программу, которая определяла бы минимальную стоимость распила.

Ввод из файла INPUT.TXT. В первой строке содержатся через пробел натуральные числа L (2 ≤ L ≤ 1000) и N (1 ≤ L ≤ 50, N < L) – длина бруса и число разрезов. Вторая строка содержит N натуральных чисел C_i (0<C_i<L ) через пробел, задающих в строго возрастающем порядке места, в которых нужно сделать распилы.

Вывод в файл OUTPUT.TXT.. В единственной строке вывести минимальную стоимость распилов.

3.6. Суперсчастливые билеты (8)

Известно, что «счастливым» билетом называется билет, в номере которого сумма цифр первой половины номера равна сумме цифр второй половины номера. А «суперсчастливым» называется билет, у которого кроме упомянутого условия каждая цифра отличается от соседней не более чем на 1 (например, 323233) . Номер может начинаться с 0. Найти количество «суперсчастливых» номеров среди всех 2N-значных билетов (1 ≤ N ≤ 11).

Ввод. Единственная строка содержит значение N.

Вывод. Единственная строка содержит количество номеров.

Примеры

Ввод 1 Ввод 2

3 4

Вывод 1 Вывод 2

220 1296