silent__killer1's blog

ncr for large N ( n<=1e9)
By silent__killer1, history, 6 years ago, In English

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.

  • Vote: I like it
  • -11
  • Vote: I do not like it

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

What is ncr?

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

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.

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +39 Vote: I do not like it

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

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

    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;

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

      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.

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

        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!

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

          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

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

            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.

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

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

                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.

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

                  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.

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

You can refer to editorial of this problem.

→ Reply