369. Комбинации

Сколькими способами можно выбрать m из n вещей?

Вход. Каждая строка содержит два числа n и m. Перед первым, после первого и после второго числа может находиться произвольное количество пробелов. Известно, что 5 £ n, m £ 100, m £ n.

Выход. Для каждого теста вывести в отдельной строке фразу: “N things taken M at a time is C exactly.”. Значение C равно количеству способов, которыми можно выбрать m из n вещей. Известно, что значение C помещается в 32-битовом типе int.

Пример входа

100 6

20 5

18 6

0 0

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

100 things taken 6 at a time is 1192052400 exactly.

20 things taken 5 at a time is 15504 exactly.

18 things taken 6 at a time is 18564 exactly.

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Значение биномиального коэффициента вычислим по формуле:

= =

По условию задачи значение не больше 2³¹ – 1, но в процессе вычислений значения текущих переменных могут выходить за границы типа int. Поэтому для временных переменных будем использовать 64-битовый тип long long. Если значение m близко к n, следует воспользоваться свойством = , чтобы не получить Time Limit.

Реализация алгоритма

Функция Cnm(m, n)вычисляет значение биномиального коэффициента .

int Cnm(int m, int n)

{

long long i, res = 1;

if (m > n - m) m = n - m;

for(i = 1; i <= m; i++)

res = res * (n - i + 1) / i;

return (int)res;

}

Основной цикл программы. Читаем значения n и k и выводим значение Cnm(m, n).

while(scanf("%d %d",&n,&m), n + m)

printf("%d things taken %d at a time is %d exactly.\n",n,m,Cnm(m,n));