Question

C语言排列组合问题的快速算法

求C(m,n)，即n!/(m!*(n-m)!)，结果对1000000007取模。
需要解决伪溢出问题，最高效率的算法是什么。

Answer 1

#include "math.h"
typedef unsigned int uint32;
uint32 C(uint32 m, uint32 n)
{
	double res = 0;
	uint32 i, ires;
	for (i = n-m+1; i <= n; i++) res += log(i);
	for (i = 2; i <= m; i++)     res -= log(i);
	res = exp(res);
	ires = (uint32) res;
	if ((uint32)(res + 0.5) != ires ) ires++;
	return ires % 1000000007;
}
int main()
{
    printf("C(2,3) = %d C(2, 10) = %d C(3, 1000)= %d\n",
	C(2,3), C(2, 10), C(3, 1000));
	return 0;
}