AmericanPsycho's blog

Compute binomial coefficients

By AmericanPsycho, history, 7 years ago, In English

Hi everyone.

Lately I've done some combinatorial problems. And I am wondering.
What methods are used to calculate the binomial coefficients?
What is the most effective?

I have used dynamic programming, although it is effective for many
queries and can be modulated with any number, the range is too limited.


When the number is a bit higher, I have used modular arithmetic
but I need to precalculate all factorials and is needed a prime number
as a module and really the range is not so large just 10 ^ 5 maybe.
If the problem have higher numbers, I'm lost

Can you tell me what techniques you use and when they can be used are?
I hope you can help me
Thank you

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

Comments Comments (13)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

Sorry, I didn't read your blog fully

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In nCr mod p if numbers are large(upto 10^18) and p is not a prime number. So in that case: p = a1^b1*a2^b2*a3^b3....an^bn. so in that case find nCr mod (a1^b1), nCr mod(a2^b2) till nCr mod(an^bn) using lucas theorem and further use CRT to get the end result. Problem link: https://www.codechef.com/MAY17/problems/SANDWICH

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

Contest finished, I'm ready to give solution for your question:

You can find C(n, r) in O(log(MOD)) time with O(n) precalculating. Read about modular inverse of number, precalculate factorials, then use formula:

intt InverseEuler (intt n, intt MOD) {
    return powmod(n, MOD-2, MOD);  /// here powmod means binary exponentiation
}

intt C(intt n, intt r, intt MOD) {
    return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can precalculate modular inverses in O(N) and you can find C(n, r) in O(1).

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

      Yes, but code will be O(nlogn) anyway.

      If there are queries, precalculating will be nice optimization.

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

        Nope, it will be O(N + log(MOD)).

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

          If you calculate inverses of factorials then how can you do in O(n)? I know a way to calculate all modular inverses from 1 to Mod, in O(MOD)

          Then Pre-calculation will take O(n log MOD) too!

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

    This is not what he's asking for :) he says that he already knows this.

    → Reply