I want to find nCr(n choose r, if you will) modulo a prime. The trouble is that all the numbers i.e. n, r and prime are large and are of the order of 10^9.
One method I could come up with is computing each of the three factorials individually(using FFT and multipoint evaluation) but that seems too tedious. It may also timeout.
Is there anything else I can do ?
There is an ongoing competition with the same problem... :)
Well the same problem was already given on a past codechef competition less than a year ago (exactly this was asked — find
with big N and K).
It's contest author's fault for using something which was already given a few months ago. Even if it isn't answered here one could easily find an explanation on how to find
for big values of N and K by spending 15 minutes or less in google searching. There are actually at least 2 such blogs on CF.
I can't use Lucas' theorem if that's what you're talking about. It's because p is too large.
Problem
In my version, prime is of the order of ~10^9 not 10^6
Really, where are those blogs, where N, K and mod are around 10^9 — 2*10^9? When I was solving the same problem in the ongoing competition, I could not find anything, so I came up with the solution. However, it would be interesting to see what other alternative solutions are.
Can you share the link of that problem? previously I thought that the case of computing nCk % p such that n,k,p <=10^9 can't be solved.
Sure. https://www.hackerearth.com/challenge/competitive/october-circuits-17/algorithm/army-parade-7bcfea8e/
Well, the multipoint evaluation approach mentioned by the OP is one method (
).
This problem is from an ongoing contest.
Can anyone explain the intended solution, now?
The editorial mentions caching factorials for 0, 106, 2 × 106, 3 × 106, ...!
How can this be achieved (once we have this it is easy to get factorials upto 2 × 109) efficiently?
Lets say you need to find x! where 2*109 > x.
Now, we have stored 0! , 106 ! , 2*106 !, 3*106 ! .... and so on till 2000*106 ! .
Now there will exist some integer 'z' such that z*106 <= x <= (z+1)*106.
Since 'z' will always be <=2000, we would have already calculated z*106!
Now note that the difference between (z+1)*106 and z*106 is 106.
Therefore we would need to multiply the pre-calculated z*106! value by atmost 106 integers.