if n is or range 10^9 or so. and k is of the range <= 20, 50, 100 or so.

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