Вычисление больших комбинаций

Как бы вы вычислили такую ​​комбинацию, как (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» для больших входов. Может быть, я скучаю по проблеме?