I want to find nCr Mod p where n,r is big integer <= 10^6 and P is a prime number, how can i do this ?
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | adamant | 164 |
2 | awoo | 164 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | pajenegod | 145 |
9 | orz | 145 |
I want to find nCr Mod p where n,r is big integer <= 10^6 and P is a prime number, how can i do this ?
Name |
---|
nCr(mod p) = n!(mod p) * inv(r!(mod p)) * inv((n-r)! Mod p) % p where n! (mod p) can be calculated in linear time and inverse n! modulo p can be calculated in O(nlogp) time for all n(preprocessing).
You can calculate inverse n! mod p in linear time in kind of a hacky way.
Let's say you want to calculate $$$n!^{-1}$$$ up to MAXN. First, calculate $$$MAXN!^{-1}$$$ offline. Now, loop down from MAXN down to 1, doing $$$n!^{-1}*n = (n-1)!^{-1}$$$.
For a less hacky way, you can calculate all the modular inverses up to n with:
Then simply use another loop to calculate prefix products of this. See this blog for why it works.
Of course, it's going to have a worse constant than the hacky way because of all the % operations, but I haven't tested exactly how much worse it is. I'm guessing not enough to matter for the average problem, and it's certainly better than the O(nlogp) way.
How $$$n!^{-1}$$$ * $$$n$$$ = $$$(n-1)!^{-1}$$$
$$$n!^{-1} * n \equiv n^{-1} * (n - 1)^{-1} * n \equiv n * n^{-1} * (n - 1)^{-1} \equiv (n - 1)^{-1} \pmod{m}$$$
try using Lucas's Algorithm. Hope it helps!
nCr % p using Fermat Little Theorem Hope this helps you .