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

Binomial coefficients of large numbers modulo prime
Автор Eddagdeg, история, 6 лет назад, По-английски

Hello coders! let's suppose we have three numbers n,k,mod=1e9+7 where n,k<=1e9 how to calculate nCk %mod! any hint please! Thanks^__^

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

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

You can calculate N! in O(log(N)) using Matrix Multiplication, then calculate N! / [ K! * (N &mdash; K)! ] % mod How ? (only when mod is prime)

(A / B) % mod = A * Pow(B, mod &mdash; 2) % mod
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Another approach is precalculate 106!, (2·106)!, ..., 109! locally and paste it in your code. Then you can easily calculate every factorial using 106 multiplications.

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

Way 1: Precalculate the factorials. Then, use Fermat's Little theorem, which says that says that $$$a^{-1} \equiv a^{p - 2} \pmod{p}$$$. This allows us to sort of transform modular division into modulo multiplication and then some powers. The pre-computing factorial is $$$O(n)$$$, dealing with the denominator is $$$O(\log(N))$$$ if you use fast exponentiation.

Way 2: Pascal's Identity. Straight forward dynamic programming. This is $$$O(n^2)$$$.

Optimization: Use Lucas's theorem.

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

    I think you didn't realize that $$$n = 10^9$$$ which makes pre computing of factorials $$$O(n)$$$ is impossible within time and memory limit

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

      I was speaking generally, which is why I included Way 2, which is clearly too slow. I think with Lucas's theorem, Way 1 would be sufficiently fast, though.

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

    How would you optimize it using Lucas's theorem?

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

You can calculate C(n,k) = n! * reverse((n — k)!) * reverse(k!) which reverse(a) = power(a, mod — 2)

If you have enough memory, you can save first a! into an array

→ Ответить