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

ncr for large N ( n<=1e9)
Автор silent__killer1, история, 5 лет назад, По-английски

Hi ,I need to compute ncr for (n) from 1<=n<=1e9 where (n-r) are from 1<=n-r<=1e6 . Mod 1e9+7.I googling about this and get to know that this could be done by (lucas theorem) I try to implement but fails . So if anyone could help me in this it would be grateful.And please share your code for this.Thankyou.

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

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

What is ncr?

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

I don't know if this is fast enough for your case but it might be:

  1. Write a brute force program to compute all factorials of the form $$$y!$$$ such that $$$y$$$ is a multiple of $$$X$$$ and put them in a static array $$$Y$$$ in your real program.
  2. To compute any factorial of the form $$$z!$$$, find the largest element $$$e$$$ of the form $$$k!$$$ in $$$Y$$$ such that $$$k \leq z$$$, and then iterate from $$$k+1$$$ to $$$z$$$ and multiply all these numbers by $$$e$$$.

The complexity of calculating any NCr would be $$$O(X)$$$ and the memory complexity (for the static array) would be $$$O(\frac{N}{X})$$$, so maybe $$$X = 10^6$$$ is enough.

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

I don't understand why this problem is so hard. I think it is fairly easy. Notice the constraint $$$n-r \le 10^6$$$. You can easily calculate value of $$$C(n,r)$$$ in $$$O(r)$$$. For further explanation, see hint.

Hint

Lastly, you need to remember that $$$C(n,r) = C(n,n-r)$$$, hence if $$$n-r \le 10^6$$$, then you should calculate $$$C(n,n-r)$$$ instead of calculating $$$C(n,r)$$$.

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

    Didn't get the last part...

    https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/ Why this : if ( k > n — k ) k = n — k;

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

      That is exactly what I wrote in the last line.

      Since $$$C(n,r) = C(n,n-r)$$$, it means, when calculating $$$C(n,k)$$$, if $$$ n-k < k $$$, then it is better ( faster ) to calculate $$$C(n,n-k)$$$, assuming you are using a linear algorithm.

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

        If i use k as k even if k>n-k, will it work ?

        It's giving me WA on this problem if i dont replace k with n-k if k>n-k

        https://www.spoj.com/problems/MARBLES/ (code: https://ide.codingblocks.com/s/142841)

        Thanks!

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

          Well, you need to understand that $$$(n-i+1)/i$$$ might not always be an integer. You might be losing precision, due to integer division. Honestly, I don't understand how putting that line is giving you an AC.

          Also, calculating the whole factorial would overflow. You need to only divide if it's divisible.

          Link : here

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

            Actually I tried to check if (n-i+1)/i fails to be an integer... But failed.

            Maybe it stays an integer... I cant find any exception.

            Maybe putting that line prevents it somehow... I dont see how.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +22 Проголосовать: не нравится 
              int ans=1;
    for(int i=1;i<=r;i++){
        ans=ans*(n-i+1)/i;
    }

              This code is perfectly fine unless the answer exceeds the range of int. It works because product of r consecutive integer is always divisible by r!.

              so (ans*(n-i+1)) is divisble by i. and the expression is actually getting evaluated in order ans = (ans*(n-i+1))/i. so integer division is not a problem, unless ans exceeds the range of int.

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

                Try your code with n = 65536 and r = 2.

                The answer should be 2147450880, which fits within integer limit, but your code gives wrong output.

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

                  Thats because ans*(n-i+1) is overflowing before getting divided by 2.

                  i think i wrote the word, its not the answer that exceeds int but variable ans that exceeds int.

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

You can refer to editorial of this problem.

→ Ответить