×

How to work with huge factorials?

 0 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? asked 11 Jul, 03:32 3★ay2306 192●9 accept rate: 13% How to work means ? What u wanna ask ? Share the problem link for more help... (11 Jul, 11:34) 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!}$ (11 Jul, 12:45) ay23063★ but u r working on a problem of CF right... so I was asking for that question link.. (11 Jul, 20:02)

 1 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 : https://cp-algorithms.com/combinatorics/binomial-coefficients.html answered 11 Jul, 17:51 3★pk301 627●10 accept rate: 16%
 1 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... answered 11 Jul, 20:01 1.2k●1●9 accept rate: 27%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×189
×47