Finding nCk effectively

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.

 

	#include <bits/stdc++.h>
	using namespace std;
	#define FOR(i,a,b) for (int i = (a); i < (b); i++)
	#define REP(i,n) for(int i = 0; i < (n); i++)
	#define SZ(x) ((int)((x).size()))
	#define ALL(c) (c).begin(),(c).end()
	#define PB push_back
	#define MP make_pair
	#define FILL(a,v) memset(a,v,sizeof(a))
	#define FF first
	#define SS second
	#define DEBUG(a) cerr <<#a<<" : " << a<<endl;
	typedef long long LL;
	typedef long double LD;
	typedef vector<int> VI;
	typedef vector<string> VS;
	typedef pair<int,int> PII;
	// Main code starts Now.
	LL mod = 2004;
	map <pair <LL, LL> , LL> mp;
	/*
	// This is another cool method.
	LL ncr (LL n, LL k) {
	if (mp.find (MP (n, k)) != mp.end())
	return mp[MP (n, k)];
	if (n < 0 || k < 0) return 0;
	if (k > n) return 0;
	if (n == 0) {
	if (k == 0)
	return 1;
	else
	return 0;
	}
	if (n & 1) {
	LL ans = (ncr (n - 1, k) + ncr (n - 1, k - 1));
	if (ans >= mod)
	ans -= mod;
	mp[MP(n, k)] = ans;
	return ans;
	} else {
	LL ans = 0;
	REP (j, k + 1) {
	LL temp = (ncr (n / 2, j) * ncr (n / 2, k - j));
	temp %= mod;
	ans += temp;
	if (ans >= mod)
	ans -= mod;
	}
	mp[MP (n, k)] = ans;
	return ans;
	}
	}
	*/
	LL A[15];
	vector <pair<int, int> > fact[15];
	LL ncr (LL p, LL q) {
	if (q > p)
	return 0;
	if (q == 0)
	return 1;
	REP (i, q) {
	A[i] = p - i;
	}
	REP (i, SZ(fact[q])) {
	int tot = fact[q][i].second;
	REP (j, q) {
	while (tot && A[j] % fact[q][i].first == 0) {
	tot --;
	A[j] /= fact[q][i].first;
	}
	}
	assert (tot == 0);
	}
	LL ans = 1;
	REP (i, q) {
	ans *= A[i];
	ans %= mod;
	}
	return ans;
	}
	int isPrime (int n) {
	for (int i = 2; i * i <= n; i++)
	if (n % i == 0)
	return false;
	return true;
	}
	int getAns (int n, int k) {
	int ans = 0;
	while (n) {
	ans += (n / k);
	n /= k;
	}
	return ans;
	}
	int main () {
	vector <int> prime;
	REP (i, 11) {
	FOR (j, 2, 11) {
	if (isPrime (j)) {
	int tot = getAns (i, j);
	// cout << i << " " << j << " " << tot << endl;
	if (tot > 0)
	fact[i].PB (make_pair (j, tot));
	}
	}
	}
	for (int i = 0; i <= 10; i++) {
	for (int j = 0; j < fact[i].size(); j++) {
	cout << fact[i][j].first << " " << fact[i][j].second << " , ";
	}
	cout << endl;
	}
	LL N, M;
	while (scanf ("%lld %lld", &N, &M) != EOF) {
	cout << ncr (N, M) << endl;
	}
	return 0;
	}

view raw nCk.cpp hosted with ❤ by GitHub

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 :(