### silent__killer1's blog

By silent__killer1, history, 2 years ago,

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

 » 2 years ago, # |   0 Auto comment: topic has been updated by silent__killer1 (previous revision, new revision, compare).
 » 2 years ago, # |   -11 What is ncr?
 » 2 years ago, # | ← Rev. 2 →   0 rng_56 would help
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I am asking when n max upto 1e9.Your code gives tle for that.... Need a better aporoach.
 » 2 years ago, # | ← Rev. 2 →   +12 I don't know if this is fast enough for your case but it might be: 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. 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.
 » 2 years ago, # | ← 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. 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)$.
•  » » 2 years ago, # ^ |   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;
•  » » » 2 years ago, # ^ |   +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.
•  » » » » 2 years ago, # ^ | ← 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 Thanks!
•  » » » » » 2 years ago, # ^ | ← 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
•  » » » » » » 2 years ago, # ^ |   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.
•  » » » » » » » 2 years ago, # ^ |   +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.
•  » » » » » » » » 2 years ago, # ^ |   -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.
•  » » » » » » » » » 2 years ago, # ^ |   0 I am getting the correct answer... with this code: https://ide.codingblocks.com/s/142841note that it is computing C(n-1, r-1)
•  » » » » » » » » » 2 years ago, # ^ | ← 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.
 » 2 years ago, # |   0 You can refer to editorial of this problem.