choose.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned long long
choose_i(unsigned long const n, unsigned long const r, unsigned long long* const memo)
{
#define index_(n_, r_) ((r_)+(n_)*((n_)+1)/2)
  if (r > n)
    return 0;
  if (memo[index_(n, r)] == 0) {
    if (r == 0 || r == n)
      return (memo[index_(n, r)] = 1);

    if (r-1 == 0) memo[index_(n-1, r-1)] = 1;
    else          choose_i(n-1, r-1, memo);
    if (r == n-1) memo[index_(n-1, r  )] = 1;
    else          choose_i(n-1, r, memo);
    memo[index_(n, r)] = memo[index_(n-1, r-1)] + memo[index_(n-1, r)];
  }
  return memo[index_(n, r)];
#undef index_
}

unsigned long long
choose(unsigned long const n, unsigned long const r)
{
  unsigned long const memo_n = (r+n*(n+1)/2+1);
  unsigned long long* const memo = (unsigned long long*)malloc(sizeof(unsigned long long)*memo_n);
  memset(memo, 0, sizeof(unsigned long long)*memo_n);
  unsigned long const y = choose_i(n, r, memo);
  free(memo);
  return y;
}

int
main(int argc, char** argv)
{
  unsigned long const n = strtoul(argv[1], NULL, 10);
  unsigned long const r = strtoul(argv[2], NULL, 10);
  printf("%llu\n", choose(n, r));
  return 0;
}