Calculate nCr (n, m) mod k for large n effectively
I need to compute nCr(n,m) % k
for large n
( n <= 10^7)
).
Here's my attempt:
int choose(int n, int m, int k) {
if (n==m || m==0)
return 1 % k;
return (choose(n-1, m-1, k) + choose(n-1, m , k)) % k;
}
It calculates a number of mod k: combinations nCr(n,m) % k
using the pascals identifier .
It's too inefficient for large n
(try choose(100, 12, 223092870)
) ones, I'm not sure if memoization would speed it up or if a completely different set-theoretic approach is needed.
I need this to execute efficiently for large numbers instantly, so I'm not sure if memos are the solution.
Note: k
Shouldn't be easy!
source to share
This happens now and then in programming contests, one of the common ways to solve this problem is using Lucas's theorem and the Chinese theory of remains.
@DAle posted a helpful resource with details: http://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/
source to share
Since nPr has an explicit formula nPr(n, m) = n!/((n-m)!)
, you should try using that instead. My advice:
- Remember n! = N * (n-1) * ... * 2 * 1
- Note that a while loop (yes, a loop, not a recursion ^^) can greatly optimize the computation (division cancels out many factors, leaving you with multiplication
nPr(n, m) = n*(n-1)*...*(n-m+2)*(n-m+1)
)
Finally, you must calculate the modulus after calculating nPr (n, m) to avoid redundant modulo operations.
If that helps, you can try to formulate a loop invariant , which is pretty much a statement that must be true for all valid values of n
and m
.
Hope it helped :)
EDIT
I figured out what you said nCr after I wrote my answer. For nCr, you can add another while loop after evaluating nPr, which simply computes m!
, divides nPr by m!
, and then replaces this answer instead. All in all, this will give an O (n) algorithm which is fairly scalable. It also uses very little memory.
source to share