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

Compute binomial coefficients

Автор AmericanPsycho, история, 7 лет назад, По-английски

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

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

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

Sorry, I didn't read your blog fully

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

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

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

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;
}
→ Ответить