hars123's blog

needed help in precomputation of binomial coefficient

By hars123, history, 7 years ago, In English

the constraints for n and k are upto 10^6. I wanted to efficiently precompute all the binomial coefficient (n choose k) and store them somewhere for further use. Please help me!. Thanks in advance!.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

That will require O(n2) memory which will surely MLE for n = 106. But you can precompute factorials and inverse factorials and store them in an array. Then after doing this you can calculate any binomial coefficient in O(1) time.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I don't understand what do you mean by inverse factorial when the question didn't mention taking modulo (it must be given, otherwise large answers).

    Assuming modulo: Assuming modulo is a prime, use extended euclid or fast expoentiation for inverses else use Chinese remainder theorum to break modulo. Or lucas theorum may be used to break number in case of prime modulo.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

You can't actually store them. You don't seem to have any idea how large it can be.
Example:
If you want to store all of them, then sum of number of digits will be approximately -

That is gonna cost you 300 GB of memory. Good luck finding that much RAM ;)

If you want them modulo some number then reffer to the above comment.

→ Reply