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

Asking about calculating nCk
Автор ldn694, история, 2 года назад, По-английски

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.

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

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

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

    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)$$$?

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

      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$$$.

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

        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

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

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

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

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

            → Ответить