Блог пользователя hars123

needed help in precomputation of binomial coefficient

Автор hars123, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

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.

→ Ответить