c++ - 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 函数(例如 bignums 的乘法和除法)，因为它是一门微妙的算法学科(您仍然可以获得这方面的博士学位)。

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

一些语言或实现(特别是 Common Lisp 的 SBCL)提供了 native bignum 操作。但标准 C 或 C++ 不会。