C中的ncr (组合)

Question

我正在尝试使用dp来计算c中的ncr(组合)。但它在n=70上失败了。有人能帮上忙吗？

unsigned long long ncr( int n , int r)
{
unsigned long long c[1001];
int i=1; 
c[0]=1;
for(i=1; i<=r; i++)
    c[i]= ((unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1))%(unsigned long long) (1000000007)/ (unsigned long long)(i);
return c[r];
}

基本思想是ncr = ((n-r+1)/r)* nc(r-1)

Answer 1

中间产品(unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1)是一个非常大的数字，它溢出了64位字。

您可能想要使用bignums。我强烈建议不要开发自己的bignum函数(例如大数的乘法和除法)，因为这是一个微妙的算法主题(你仍然可以得到一个关于它的PhD )。

我建议使用一些现有的bignum库，比如GMP。

一些语言或实现(特别是用于Common Lisp的SBCL )提供了本机bignum操作。但标准C或C++不需要。

Answer 2

在乘法之前做除法运算。a *b /c = (a/c) *b第二个更适合溢出，这似乎是你的问题。