本文介绍了NCR在C(组合)的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我米尝试使用DP在C来计算NCR(组合)。但它是在n = 70失败。谁能帮助?

I m trying to calculate ncr(combinations) in c using dp. But it is failing with n=70. Can anyone help?

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)

basic idea is ncr = ((n-r+1)/r)* nc(r-1)

推荐答案

中间产物(无符号长长)(C I-1)*(无符号长长)(N-1 + 1)是一个非常大的数字,并溢出64位字。

The intermediate product (unsigned long long) (c[i-1]) * (unsigned long long)( n-i+1) is a very big number, and is overflowing the 64 bits word.

您可能需要使用。我强烈反对开发自己的BIGNUM功能(例如,乘法和大数司),因为它是一个微妙的算法主体(你仍然可以得到一个关于博士)。

You may want to use bignums. I strongly recommend against developing your own bignum functions (e.g. multiplication and division of bignums), because it is a delicate algorithmic subject (you could still get a PhD about that).

我建议使用一些现有的BIGNUM库如。

I suggest using some existing bignum library like GMP.

一些语言或实现(尤其是获得Common Lisp的)提供了本地BIGNUM操作。但是,标准C或C ++没有。

Some languages or implementations (in particular SBCL for Common Lisp) offers native bignum operations. But standard C or C++ don't.

这篇关于NCR在C(组合)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-14 09:13