UVa 369

Summary

You are required to evaluate ${\displaystyle (^{n}C_{m})}$ which is equal to ${\displaystyle {\frac {n!}{m!*(n-m)!}}}$

Explanation

Consider the following example: ${\displaystyle (^{100}C_{6})}$

${\displaystyle {\frac {100!}{(100-6)!*6!}}=}$ ${\displaystyle {\frac {100!}{94!*6!}}=}$ ${\displaystyle {\frac {94!*95*96*97*98*100}{94!*6!}}}$

Cancel 94!

${\displaystyle {\frac {95*96*97*98*99*100}{2*3*4*5*6}}}$

Cancel 96 with 2*6 = 8 and 99 with 3 = 33 and 100 with 4*5 = 5

${\displaystyle 95*8*97*98*33*5=1192052400}$

Gotchas

You should cancel and simplify the formula as much as possible, to avoid overflow.

Notes

The result of ${\displaystyle (^{n}C_{m})}$ will fit in a 32-bit int

Implementations

Using long int in storing the result should be enough.

Optimizations

Just Simplify the formula to fit in a 32-bit int.

Alternative solution

Generate Pascal's triangle by using addition and then just do a simple lookup for each of the queries. It's a simpler method which is also much faster.

Input

20 5
18 6
15 7
10 5
100 100
40 5
0  0


Output

20 things taken 5 at a time is 15504 exactly.
18 things taken 6 at a time is 18564 exactly.
15 things taken 7 at a time is 6435 exactly.
10 things taken 5 at a time is 252 exactly.
100 things taken 100 at a time is 1 exactly.
40 things taken 5 at a time is 658008 exactly.


References

Hussein Al Sayed 04:11, 28 August 2008 (UTC) http://www.algorithmist.com/index.php/Category:Math