1) Calculating nCk: simply calculate:
numerator = n(n-1)...(n-k+1)
deno = k(k-1)...k!
ans = num/deno
But what if num and deno is high and over flow may occur, you can use
nCk = nC(k-1) (n-k+1)/k repeatedly. . Both can be calculated in O(k) steps
2) With modulo involved, suppose you are calculating modulo a big prime P. Then we know Z_p is a field and therefore multiplicative inverse exist i.e. for any number x<P, there exist x^-1 also less than P s.t. (x*x^-1)%P = 1.
So, to find nC(k-1)*(n-k+1)k^-1, we need to find k^-1.
Before moving on let's review the fermat's little theorem, which states that for any a<p, a^(P-1) %P= 1. (The theorem is valid for a>p as well, but for our case a<p suffices). P is a prime here. So what is k^-1%P?
k^(P-1)%P = 1 => k^-1 = k^-1k^(P-1) = k^(P-2)
numerator = n(n-1)...(n-k+1)
deno = k(k-1)...k!
ans = num/deno
But what if num and deno is high and over flow may occur, you can use
nCk = nC(k-1) (n-k+1)/k repeatedly. . Both can be calculated in O(k) steps
2) With modulo involved, suppose you are calculating modulo a big prime P. Then we know Z_p is a field and therefore multiplicative inverse exist i.e. for any number x<P, there exist x^-1 also less than P s.t. (x*x^-1)%P = 1.
So, to find nC(k-1)*(n-k+1)k^-1, we need to find k^-1.
Before moving on let's review the fermat's little theorem, which states that for any a<p, a^(P-1) %P= 1. (The theorem is valid for a>p as well, but for our case a<p suffices). P is a prime here. So what is k^-1%P?
k^(P-1)%P = 1 => k^-1 = k^-1k^(P-1) = k^(P-2)
No comments:
Post a Comment