# SPOJ MARBLES

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