78 (MARBLES) - Marbles
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.
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.
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