ldn694's blog

Asking about calculating nCk
By ldn694, history, 2 years ago, In English

Hi Codeforces, I'm wondering is it possible to calculate $$$C_n^k$$$ modulo $$$m$$$ with $$$n \leq 10^9, k \leq 10^5, m \leq 10^9$$$. I've already known that if $$$m$$$ is a big prime number (for example $$$10^9+7$$$), we can easily have an $$$O(k) \cdot log_2(m)$$$ algorithm using Fermat's little theorem to find the inverse modulo of number from $$$1$$$ to $$$k$$$. If $$$n$$$ is small (for example $$$n \leq 10^6$$$), we can use sieve to get rid of the dividing step, but if $$$n$$$ is big, I have no clue. Thanks in advance.

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

Comments Comments (6)
| Write comment?
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You can loop over prime factors of $$$m$$$ to make the terms in the numerator and the denominator coprime with $$$m$$$ and keep track of the highest power of each prime dividing the answer. This should be fast enough.

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

    I still haven't figured it out. Can you explain more about the part where you say make the terms in the numerator and the denominator coprime with m pls. Does it mean dividing each number $$$i$$$ from $$$1$$$ to $$$k$$$ in the denominator and from $$$n-k+1$$$ to $$$n$$$ in the numerator by $$$gcd(i,m)$$$?

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

      Basically something like this: store integers from $$$1$$$ to $$$k$$$ in an array and $$$n - k + 1$$$ to $$$n$$$ in another array. For each prime factor of $$$m$$$, keep dividing each element in this array while it is divisible by it, and keep track of the highest exponent of each prime dividing the numerator and denominator. Now both arrays have everything coprime to $$$m$$$, so you can divide the product (modulo $$$m$$$) of the first array by the product (modulo $$$m$$$) of the second array by computing $$$\phi(m)$$$ and using Euler's theorem. Then for each prime, multiply the answer by the corresponding prime power modulo $$$m$$$.

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

        Sorry for asking but I cannot fully understand your explanation. The first part is you try to extract all the prime factors of m out of both numerator and denominator. And then (numerator/denominator by modulo m) can be done by Euler's function. But for the last part multiply the answer by the corresponding prime power modulo m, what if the prime factor of denominator has higher factor than the numerator. For example, with prime factor p of m, numerator extract p^x1 and denominator p^y1 (x1<y1). How can I compute the answer as (ans/(p^(y1-x1))) mod m

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

          This will never be the case, since binomial coefficients are integers.

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

            Thank you for your fast response, I did not think about it carefully, yes that will never happen ^.^

            → Reply