Cacher is the code snippet organizer for pro developers

// Binomial Coefficient
// Non-DP method, for when bottom-up DP with:
// C(n, k) = C(n - 1, k - 1) + C(n - 1, k), is not feasible
ll C(int n, int k) {
  if (k == 0 || k == n) return 1;
  k = min(k, n - k);  // Since C(n, k) == C(n, n - k)
  ll ans = 1;
  for (ll i = 1; i <= k; i++) {
    ans *= (n - k + i) / i;
  }
  return ans;
}