Binomial Coefficient
Implementation stolen from: https://cp-algorithms.com/combinatorics/binomial-coefficients.html#improved-implementation
int C(int n, int k) {
double res = 1;
for (int i = 1; i <= k; ++i)
res = res * (n - k + i) / i;
return (int)(res + 0.01)
A simple recursive implementation
ll choose(n, k) {
if k == 0 return 1
return (n * choose(n - 1, k - 1)) / k
}
Another Note:
Recently, I tried to use this formula for this Codeforces problem https://codeforces.com/contest/1999/submission/277997377, but I ran into integer overflow problems, even after using long long
.
They do something like this in the solution https://codeforces.com/blog/entry/132373 (Problem F) This is the tourist solution https://codeforces.com/contest/1999/submission/274741514
Yes, actually, CP algorithms teaches how to tackle this.
Factorial module MOD
The modular inverse here
int inv(int a) {
return a <= 1 ? a : MOD - (long long)(MOD/a) * inv(MOD % a) % MOD;
}
factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {
factorial[i] = factorial[i - 1] * i % MOD;
}
ll C(ll n, ll k) {
return factorial[n] * inv(factorial[k] * factorial[n - k] % MOD) % MOD;
}