c++ - c中的ncr（组合）

Question

我正在尝试使用 dp 在 c 中计算 ncr(combinations)。但它在 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 函数（例如 bignums 的乘法和除法），因为它是一门微妙的算法主题（你仍然可以获得相关的博士学位）。

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

一些语言或实现（尤其是用于 Common Lisp 的SBCL）提供了本机 bignum 操作。但标准 C 或 C++ 没有。

Answer 2

Make the division before the multiplication. a*b/c = (a/c) *b where the second better for overflow which seems your problem.