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 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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 .