From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/binomial2.cpp | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 math/binomial2.cpp (limited to 'math/binomial2.cpp') diff --git a/math/binomial2.cpp b/math/binomial2.cpp new file mode 100644 index 0000000..2ddcfe9 --- /dev/null +++ b/math/binomial2.cpp @@ -0,0 +1,32 @@ +constexpr ll mod = 1000000009; + +ll binomPPow(ll n, ll k, ll p) { + ll res = 1; + if (p > n) { + } else if (p > n - k || (p * p > n && n % p < k % p)) { + res *= p; + res %= mod; + } else if (p * p <= n) { + ll c = 0, tmpN = n, tmpK = k; + while (tmpN > 0) { + if (tmpN % p < tmpK % p + c) { + res *= p; + res %= mod; + c = 1; + } else c = 0; + tmpN /= p; + tmpK /= p; + }} + return res; +} + +ll calc_binom(ll n, ll k) { + if (k > n) return 0; + ll res = 1; + k = min(k, n - k); + for (ll i = 0; primes[i] <= n; i++) { + res *= binomPPow(n, k, primes[i]); + res %= mod; + } + return res; +} -- cgit v1.2.3