C++:组合/多集函数(因子溢出)

Question

我必须实现一个问题,该问题计算来自一组n个元素的m个元素的组合和多个集合.它们的公式如下:

问题是,使用阶乘很容易溢出,所以基本上解决这个问题的解决方案是什么？

由于它是TopCoder中问题的子问题,我有以下约束:

1)程序必须用C++编写.

2)我无法加载外部库.

Answer 1

你真的不需要n!直接计算,这可能很容易被溢出.以来

C(n,m) = C(n-1, m-1) + C(n-1,m)
C(n,0) = C(n,n) =1

您可以构建一个具有大小的表,(n+1,m+1)并使用动态编程以自下而上的方式构建表.

算法伪代码可能如下:

for i ? 0 to n do  // fill out the table row wise
      for j = 0 to min(i, m) do
          if j==0 or j==i then C[i, j] ? 1 
          else C[i, j] ? C[i-1, j-1] + C[i-1, j] 
return C[n, m]

如果你声明c(n,m)是长双并且n不是那么大,这种方式应该有效.否则,您需要定义自己的BigInteger类以避免溢出并定义+运算符如何为BigIntegers工作,BigIntegers通常表示为字符数组或字符串.