Ниже приводится простой вариант процедур и функций длинной арифметики [2]. Такой подход неэкономичен как по памяти, так и по скорости. Память используется неэффективно, так как для записи каждой цифры используется полный байт. Длина числа не хранится, а находится при вычислениях либо просто не используется, что снижает скорость. К тому же все вычисления производятся в десятичной системе счисления. В системах счисления с основанием 2 операции целочисленного деления и нахождения остатка можно свести к битовым операциям сдвигов, которые выполняются быстрее. Тем не менее, приводимый вариант реализации длинной арифметики пригоден для большинства практических задач и прост в применении. Более полное описание проблем, связанных с длинной арифметикой, можно найти в [3].

Const

numlen = <максимальное количество знаков в длинных числах>;

{ для параметров циклов используются переменные integer,

если numlen>MaxInt, нужно использовать переменные типа word }

Type

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

{ длинное число от младших разрядов к старшим;

переменной A типа number представлено число SUM(a[i]*10^(i-1))}

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

Var

i: integer;

Begin

For i:=1 to numlen do

n[i]:=0;

End;

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

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

Var

i: integer;

Begin

Set0(n); i:=1;

While short>0 do

begin

n[i]:=short mod 10;

short:=short div 10;

i:=i+1;

end;

End;

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

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

Var

i: integer;

Begin

For i:=1 to numlen do

n2[i]:=n1[i];

End;

Function Len(var n:number): integer;

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

Var

i: integer;

Begin

For i:=numlen downto 1 do

if n[i]<>0 then

begin

Len:=i;

Exit;

end;

Len:=1;

End;

Procedure Show(var n:number);

{вывод числа и перевод строки }

Var

i: integer;

Begin

For i:=Len(n) downto 1 do

Write(n[i]);

WriteLn;

End;

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

{прибавление короткого числа}

Var

i: integer;

Begin

i:=1;

While short>0 do

begin

short:=short+n[i];

n[i]:=short mod 10;

short:=short div 10;

i:=i+1;

end;

End;

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

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

Var

i,carry: integer;

Begin

carry:=0;

For i:=1 to numlen do

begin

carry:=carry+n[i]*short;

n[i]:=carry mod 10;

carry:=carry div 10;

end;

if carry<>0 then {диагностика переполнения}

Halt(1);

End;

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

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

Var

i: integer;

Begin

rem:=0;

For i:=numlen downto 1 do

begin

rem:=rem*10+n[i];

n[i]:=rem div divisor;

rem:=rem mod divisor;

end;

End;

Procedure Add(Var n1,n2: number);

{прибавление длинного числа}

Var

i,carry: integer;

Begin

carry:=0;

For i:=1 to numlen do

begin

carry:=carry+n1[i]+n2[i];

n1[i]:=carry mod 10;

carry:=carry div 10;

end;

if carry<>0 then {диагностика переполнения}

Halt(1);

End;

Procedure Mul(Var n1,n2: number; Var n3: number);

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

Var

i1,i2,i3,len1,len2,carry: integer;

Begin

Set0(n3);

len1:=Len(n1);

len2:=Len(n2);

For i1:=1 to len1 do

For i2:=1 to len2 do

begin

i3:=i1+i2-1;

carry:=n1[i1]*n2[i2];

While carry>0 do

begin

carry:=carry+n3[i3];

n3[i3]:=carry mod 10;

carry:=carry div 10;

inc(i3);

end;

end;

End;

Function Cmp(Var n1,n2: number): integer;

{ сравнение чисел:

если n1<n2 выдает -1

если n1=n2 выдает 0

если n1>n2 выдает 1

}

Var

i: integer;

Begin

For i:=numlen downto 1 do

begin

if n1[i]<n2[i] then

begin

Cmp:=-1;

Exit;

end;

if n1[i]>n2[i] then

begin

Cmp:=1;

Exit;

end;

end

Cmp:=0;

End;

Маг. Имеется N супружеских пар. Маг должен определить, кто кому супруг. Какова вероятность угадать ровно K раз из N?

Ввод из файла INPUT.TXT. В первой задаются через пробел строке K и N (1 ≤ N ≤ 100, 0 ≤ K ≤ N).

Вывод в файл OUTPUT.TXT вероятности угадать ровно K раз из N в виде несократимой дроби либо единственного значения 0.

Примеры

Ввод 1 Ввод 2

2 5 9 10

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

1/6 0

Пусть D(N) – функция, определяющая количество перестановок из N элементов 1, 2, …, N, в которых ни один из элементов не остается на своем месте. Такие перестановки называются беспорядками. Тогда ответ задачи определяет выражение

P_NK = (C_N^K  D(N-K)) / N! = D(N-K)) / K! (N-K)! (1)

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

Очевидно, что D(1) = 0, D(2) = 1, D(3)=2 - перестановки (2, 3, 1) и (3, 1, 2).

При N = 4 существуют 9 перестановок с элементами не на своих местах:

(2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3),

(4, 3, 1, 2), (4, 3, 2, 1), т.е. D(4)=9.

Докажем приведенную в [1] без доказательства рекуррентную формулу

D(N+1) = N  ( D(N) + D(N-1)) (2)

Возможны два варианта:

1. Элемент N+1 находится на месте K, а элемент K находится на месте N+1, то есть перестановка образована обменом элемента N+1 c элементом K. Тогда все остальные N-1 элементов не на своих местах. Поскольку 1 ≤ K ≤ N, таких случаев N  D(N - 1). Например, при N+1=5 и K = 2 мы рассматриваем множество перестановок (S₁, 5, S ₃, S ₄, 2), в которых в качестве S₁, S ₃, S ₄ фигурируют элементы 1, 3, 4 и S₁ ≠ 1, S₃ ≠ 3, S₄ ≠ 4.

2. Элемент N+1 находится на месте K, а на месте N+1 находится элемент M, при этом M ≠ K. Тогда элементы 1, 2, …, M-1, M+1, …, N находятся не на своих местах, а элемент N+1 не должен быть на месте M. Поскольку 1 ≤ M ≤ N, таких случаев N  D(N). Например, при N+1 = 5 и M = 3 мы рассматриваем множество перестановок (S₁, S ₂, S ₃, S ₄, 3), в которых в качестве S₁, S ₂, S ₃, S ₄ фигурируют элементы 1, 2, 4, 5 и S₁ ≠ 1, S₂ ≠ 2, S₃ ≠ 5, S₄ ≠ 4.

Суммирование по обоим вариантам доказывает рекуррентную формулу (2). В соответствии с ней, например, D(5) = 44.

Можно получить более очевидное, но и более сложное по форме соотношение для D(N+1). Всего имеется (N+1)! перестановок из N+1 элементов. Число перестановок с единственным элементом на своем месте составляет C_N+1¹  D(N), с двумя на своих местах C_N+1²  D(N-1) и т. д. Ровно N элементов на своих местах быть не может, так как и последний элемент в этом случае на своем месте. Вычитая из общего числа перестановок количество случаев, когда хотя бы один элемент находится на своем месте, получим формулу

D(N+1)= (N+1)! - C_N+1¹  D(N) - C_N+1²  D(N-1) -…- C_N+1^N-1  D(2) – 1

Единица соответствует случаю, когда все элементы на своих местах.

Примеры:

1. N=4, K=1. Тогда S = C_N^K  D(N-K) = 42 = 8, P_NK = 8 / 4! = 1 / 3

2. N=4, K=2, S = 61 = 6, P_NK = 6/24 = 1 / 4

3. N=5, K=2, S = 102 = 20, P_NK = 20 / 120 = 1 / 6 (пример из условия)

4. N=6, K=2, S = 159 = 135, P_NK = 135 / 6! = 135 / 720 = 3 / 16

5. N=10, K=9, S = C₁₀⁹  D(1) =100 = 0, P_NK = 0