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

How can i find (nCr)Mod P
Автор pranto84, история, 6 лет назад, По-английски

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 ?

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

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

      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.

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
6 лет назад, # |
← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится
$$$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.}$$$
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

try using Lucas's Algorithm. Hope it helps!

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить