How to work with huge factorials?

general
,
1

I am working on a problem on codeforce. I came up with a method but it solves down to a formula which is

\frac{n!}{w!r!}, ! stands for factorials of number.

How can I work such problems out?

2

In any of problem if situation comes to compute the value of nCr then the contraints are set such that we can iterate over the smaller of the two factorials in denominator and compute the answer. And if we are required to calculate the value for large constraints then we must have given some modulo number and in that case we can compute the factorial of all the number and then take inverse modulo for the denominator (if the given modulo number is prime. In case it is not then we have to do a little bit of extra work.)

For code you can refer this : Binomial Coefficients - Algorithms for Competitive Programming

inverse modulus : https://www.quora.com/How-do-I-find-the-value-of-nCr-1000000007-for-the-large-number-n-n-10-6-in-C

1 Like
3

U can also go with method stated by @pk301
But some problems may require fast calculations and calculating mod inverse may be slow and It can also give wa in some cases when denominator doesn’t satisfy conditions for the method used for mod inverse and also some numbers mod inverse does not exist…
Hence, While calculating nCr if in n*r fits an 2D array… and U need to use nCr it more often in your solution then u can make a pascal’s triangle which will take O(n^2) time complexity…

1 Like
4

How to work means ? What u wanna ask ? Share the problem link for more help…

5

It’s not a specific problem. It is just like I want to calculate the formula, knowing that it will reduce to some simple natural number.
Like \frac{10!}{6!2!}

6

but u r working on a problem of CF right… so I was asking for that question link…