From 558aeeed893c98bf1851856c4effd1ac4c3722e7 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 8 May 2023 11:25:47 +0200 Subject: improved binomial --- math/binomial0.cpp | 14 ++++++++++++++ 1 file changed, 14 insertions(+) create mode 100644 math/binomial0.cpp (limited to 'math/binomial0.cpp') diff --git a/math/binomial0.cpp b/math/binomial0.cpp new file mode 100644 index 0000000..d9af917 --- /dev/null +++ b/math/binomial0.cpp @@ -0,0 +1,14 @@ +constexpr ll lim = 10'000'000; +ll fac[lim], inv[lim]; + +void precalc() { + fac[0] = inv[0] = 1; + for (int i = 1; i < lim; i++) fac[i] = fac[i-1] * i % mod; + inv[lim - 1] = multInv(fac[lim - 1], mod); + for (int i = lim - 1; i > 0; i--) inv[i-1] = inv[i] * i % mod; +} + +ll calc_binom(ll n, ll k) { + if (n < 0 || n < k || k < 0) return 0; + return (fac[n] * fac[n-k] % mod) * fac[k] % mod; +} -- cgit v1.2.3