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