SPOJ MARBLES

From Algorithmist
Jump to navigation Jump to search

78 (MARBLES) - Marbles[edit]

Summary[edit]

The problem is to choose n marbles from an infinite set containing k different marble colors with at least one of each color. Assume that marbles of equal color can't be distinguished, and the order of the marbles is irrelevant.

Explanation[edit]

This problem concerns combinations. Since you need at least one of each marble, the necessary combination is . The equation is then , however, the crux of the problem is that calculating the factorials directly will quickly overflow the largest integer data type. The solution then becomes discovering a way to cancel the terms as you accumulate the answer.


Input[edit]

The first line of the input is a number representing the number of tests cases, followed by T lines containing two numbers, n and k, where .

2
10 10
30 7

Output[edit]

1
475020