pranto84's blog

How can i find (nCr)Mod P
By pranto84, history, 6 years ago, In English

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 ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    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}$$$.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For a less hacky way, you can calculate all the modular inverses up to n with:

      inv[v] = 1;
for (int i = 2; i <= n; ++i)
    inv[i] = (p - ((p/i)*inv[p%i])%p)%p;

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      How $$$n!^{-1}$$$ * $$$n$$$ = $$$(n-1)!^{-1}$$$

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        $$$n!^{-1} * n \equiv n^{-1} * (n - 1)^{-1} * n \equiv n * n^{-1} * (n - 1)^{-1} \equiv (n - 1)^{-1} \pmod{m}$$$

        → Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it
$$$nCr = n! (r!(n-r)!)^{-1}$$$
$$$k^{p-1} \equiv 1 \text{ }(\text{mod } p) \text{ if gcd}(k, p) = 1 \text{ and } p \text{ is prime} \text{ (Fermat's little theorem)}$$$
$$$k^{p-2} \equiv k^{-1} \text{ } ( \text{mod } p)$$$
$$$nCr = n! (r! (n-r)!)^{p-2} \text{ } ( \text{mod } p)$$$
$$$\text{Time complexity } = O(n + \text{log }p)$$$
$$$\text{Watch out when } p \le n \text{ , the answer might be zero in case.}$$$
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

try using Lucas's Algorithm. Hope it helps!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nCr % p using Fermat Little Theorem Hope this helps you .

→ Reply