c++ - 计算大型组合

Question

您将如何计算组合，例如(100,000 选择 50,000)？

到目前为止，我已经尝试了三种不同的方法，但由于显而易见的原因，每种方法都失败了:

1) 动态规划——数组的大小变得如此荒谬以至于出现段错误

unsigned long long int grid[p+1][q+1];

//Initialise x boundary conditions
for (long int i = 0; i < q; ++i) {
  grid[p][i] = 1;
}

//Initialise y boundary conditions
for (long int i = 0; i < p; ++i) {
  grid[i][q] = 1;
}


for (long int i = p - 1; i >= 0; --i) {
  for (long int j = q - 1; j >= 0; --j) {
     grid[i][j] = grid[i+1][j] + grid[i][j+1];
   }
}

2) 蛮力 - 显然连 100 都在计算!不现实

unsigned long long int factorial(long int n)
{
  return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}

3) 乘法公式 - 我无法存储它们太大的值

const int gridSize = 100000; //say 100,000
unsigned long long int paths = 1;

for (int i = 0; i < gridSize; i++) {
    paths *= (2 * gridSize) - i;
    paths /= i + 1;
}

// code from (http://www.mathblog.dk/project-euler-15/)

如果它对上下文有帮助，那么它的目的是解决大输入的“通过 m×n 网格有多少条路线”问题。也许我没有解决问题？

Answer 1

C(100000, 50000) 是一个巨大的数字，有 30101 个十进制数字:http://www.wolframalpha.com/input/?i=C%28100000%2C+50000%29

显然 unsigned long long 不足以存储它。你需要一些任意的大整数库，比如 GMP:http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

否则，乘法公式应该足够好。