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!.
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!.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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.
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.
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.