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

Binomial coefficients with mod
Автор Samsam, 10 лет назад, По-английски

I always see problems that need to print the result of C(n,m) mod a prime number where C(n,m) = n!/(m!*(n-m)!) the factorial formula of binomial coefficients. I've searched for it and I found that I need to find the multiplicative inverse using extended Euclidean algorithm and I've learnt it. I hope if somebody could tell me the fastest way to find C(n,m) mod P (P is a prime) using extended Euclidean algorithm and I would be thankful if there was a code. Thanks a lot.

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

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

I don't know how to " find C(n,m) mod P (P is a prime) using extended Euclidean algorithm". But, this is the way i use to find C(n,m) mod P : - If n is small (~10^4), you can caculate C(n,m) mod p with a simple O(n^2) dynamic programming. - With bigger n, you can see problem Super Sum on this lịnk. Author used Fermat Little Theorem to calculate inverse modulo p of denominator in C(n,m).

Hope it's useful.

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

    There is also a solution with extended Euclidean algorithm. You can find more about it on e-maxx (Russian).

    But it looks like solution with Euler's Theorem is easier. We know that

    So,

    Or for prime m

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

Try this.

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

if is a prime, then .

so u can use (say)
in above formula, and

→ Ответить