if n is or range 10^9 or so. and k is of the range <= 20, 50, 100 or so.
Finding nCk % mod:
n * (n - 1) * (n - 2) * (n - k + 1) / (k !).
Do the factorisation of k! easily.
Make an array A such that A[i] = n - i, i >= 0 && i < k.
now for each prime p, let us say it has power q in k!,
Remove q powers of p from A[0] to A[k - 1].
Finally multiply all the A[i]'s and then do mod to get the answer.
Finding nCk % mod:
n * (n - 1) * (n - 2) * (n - k + 1) / (k !).
Do the factorisation of k! easily.
Make an array A such that A[i] = n - i, i >= 0 && i < k.
now for each prime p, let us say it has power q in k!,
Remove q powers of p from A[0] to A[k - 1].
Finally multiply all the A[i]'s and then do mod to get the answer.
Another method.
n C k = ((n - 1) C (k - 1) + (n - 1) C k) % mod; when n is odd.
n C k = sum over i = 0 to k. ((n / 2) C i) * ((n / 2) C (k - i)). when n is even.
This method is also included in the code, but it is not so fast :(
No comments:
Post a Comment