Binomial coefficient O(N) && O(N^2) - YessineJallouli/Competitive-Programming GitHub Wiki
Binomial coefficient in O(N) with binary exponentiation
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int mx = 1e5+7;
long long fact[mx];
long long invfact[mx];
long long fast_pow(long long a, long long b) {
long long ans = 1;
while (b > 0) {
if (b & 1)
ans = (ans*a)%mod;
a = (a*a)%mod;
b/= 2;
}
return ans;
}
long long modinv(long long a) {
return fast_pow(a, mod-2);
}
void precompute() {
fact[0] = 1;
for (int i = 1; i < mx; i++)
fact[i] = fact[i-1] * i % mod;
for (int i = 0; i < mx; i++)
invfact[i] = modinv(fact[i]);
}
long long C(int n, int k) {
if (k > n)
return 0;
return fact[n] * invfact[n-k] % mod * invfact[k] % mod;
}
int main() {
precompute();
}
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int mx = 2e3 + 7;
long long dp[mx][mx];
long long C(int n, int k) {
if (dp[n][k] != -1)
return dp[n][k];
if (k == n || k == 0)
return dp[n][k] = 1;
return dp[n][k] = (C(n-1, k) + C(n-1, k-1)) % mod;
}
int main() {
memset(dp, -1, sizeof dp);
}