组合数c(n, m) = n! / (m!.(n - m)!),
n! = elnn! = e(ln1 + ln2 + ... + lnn)
则c(n, m) = e(ln1 + ln2 + ... + lnn) / (e(ln1 + ln2 + ... + lnm).e(ln1 + ln2 + ... + lnn-m))
程序如下
#include <stdio.h>
#include <math.h>
double a[100000];//a[i] = ∑lnk(1<= k <= i)
double LogC(int n, int m)
{
return a[n] - a[m] - a[n - m];
}
int main()
{
int n, m, i;
a[0] = 0;
for (i = 1; i < 100000; i++)
a[i] = a[i -1] + log(i * 1.0);
scanf("%d%d", &n, &m);
printf("%.0lf", exp(LogC(n, m)));
}
组合恒等式:C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)