4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // number of combinations choosing k out of n
4fd800b3a8 2011-02-23        kinaba: // # you might better consider to use Pascal's triangle
4fd800b3a8 2011-02-23        kinaba: // # for comb modulo some number...
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM 350 Div1 LV2
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: LL comb(LL n, LL k)
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	k = min(k, n-k);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL c = 1;
4fd800b3a8 2011-02-23        kinaba: 	for(LL i=0; i<k; ++i)
4fd800b3a8 2011-02-23        kinaba: 		c *= n-i, c /= i+1;
4fd800b3a8 2011-02-23        kinaba: 	return c;
4fd800b3a8 2011-02-23        kinaba: }