You are not logged in. Please login at www.codechef.com to post your questions!

×

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

ay2306's gravatar image

3★ay2306
1929
accept rate: 13%

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

(11 Jul, 11:34) l_returns5★

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) l_returns5★

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

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

link

answered 11 Jul, 17:51

pk301's gravatar image

2★pk301
5218
accept rate: 17%

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...

link

answered 11 Jul, 20:01

l_returns's gravatar image

5★l_returns
1.1k18
accept rate: 27%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×178
×47

question asked: 11 Jul, 03:32

question was seen: 135 times

last updated: 11 Jul, 20:02