Eddagdeg's blog

Binomial coefficients of large numbers modulo prime
By Eddagdeg, history, 6 years ago, In English

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^__^

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks but how to calculate N! in log(n)?

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

    If you can calculate n! in O(log(n)) then you have solved prime checking in O(log3(n)) or something. See this.

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

      so we can calculate n! % mod only using linear solution?

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

        See this. The main idea is sqrt decomposition and Lagrange interpolation. The complexity is .

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

      Doesn't Wilson's theorem give a $$$\mathcal{O}(\log n)$$$ time primality check in that case?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        lol no, how you can calculate (p — 1)! % p in log(n)?

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

          The comment I was replying to said " If you could compute $$$n!$$$ in $$$\mathcal{O}(\log n)$$$ you'd have a $$$\mathcal{O}(\log^3 n)$$$ primality check". Note that no claim is made that there is a $$$\mathcal{O}(\log n)$$$ algorithm for computing the factorial.

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

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.

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

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.

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

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      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.

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

    How would you optimize it using Lucas's theorem?

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

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

→ Reply