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.

Auto comment: topic has been updated by silent__killer1 (previous revision, new revision, compare).What is ncr?

rng_56 would help

I am asking when n max upto 1e9.Your code gives tle for that.... Need a better aporoach.

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

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.

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.

HintFirstly, note that $$$C(n,k) = \dfrac{n!}{(n-k)!k!} = \dfrac{n*(n-1)*(n-2)*...*(n-k+1)}{k!} $$$

Or, equivalently, $$$C(n,k) = \dfrac{n*(n-1)*(n-2)*...*(n-k+1)}{1*2*3*...*k} = \prod\limits_{i=0}^{k-1} \dfrac{n-i}{i+1} = \prod\limits_{i=0}^{k-1} (n-i)*(i+1)^{-1}$$$

This gives linear time complexity in $$$k$$$. So you can calculate $$$C(n,k)$$$ in $$$O(k)$$$.

Note: You need to take inverse, because you need answer after modulo.

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

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;

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.

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!

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

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.

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.

Try your code with

n = 65536andr = 2.The answer should be

2147450880, which fits within integer limit, but your code gives wrong output.I am getting the correct answer... with this code: https://ide.codingblocks.com/s/142841

note that it is computing C(n-1, r-1)

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.

You can refer to editorial of this problem.