diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | math/binomial0.cpp | 2 | ||||
| -rw-r--r-- | math/test/binomial0.cpp | 21 |
3 files changed, 26 insertions, 2 deletions
@@ -4,7 +4,8 @@ TESTS = \ datastructures/test/monotonicConvexHull.test \ datastructures/test/persistent.test \ graph/test/binary_lifting.test \ - graph/test/LCA_sparse.test + graph/test/LCA_sparse.test \ + math/test/binomial0.test LATEXMK = latexmk -interaction=nonstopmode @@ -50,6 +51,8 @@ graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \ graph/binary_lifting.cpp graph/test/util.cpp graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \ graph/LCA_sparse.cpp datastructures/sparseTable.cpp graph/test/util.cpp +math/test/binomial0.test: math/test/binomial0.cpp math/binomial0.cpp \ + math/shortModInv.cpp FORCE: .PHONY: all pdf test clean cleanpdf cleantest FORCE diff --git a/math/binomial0.cpp b/math/binomial0.cpp index d9af917..f37aea5 100644 --- a/math/binomial0.cpp +++ b/math/binomial0.cpp @@ -10,5 +10,5 @@ void precalc() { 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; + return (fac[n] * inv[n-k] % mod) * inv[k] % mod; } diff --git a/math/test/binomial0.cpp b/math/test/binomial0.cpp new file mode 100644 index 0000000..d6c3a03 --- /dev/null +++ b/math/test/binomial0.cpp @@ -0,0 +1,21 @@ +constexpr ll mod = 1'000'000'007; + +#include "../shortModInv.cpp" +#include "../binomial0.cpp" + +int main() { + precalc(); + assert(calc_binom(5, -1) == 0); + assert(calc_binom(5, 0) == 1); + assert(calc_binom(5, 1) == 5); + assert(calc_binom(5, 2) == 10); + assert(calc_binom(5, 3) == 10); + assert(calc_binom(5, 4) == 5); + assert(calc_binom(5, 5) == 1); + assert(calc_binom(5, 6) == 0); + assert(calc_binom(0, 0) == 1); + assert(calc_binom(-1, 0) == 0); + assert(calc_binom(-1, -1) == 0); + assert(calc_binom(-1, -2) == 0); + assert(calc_binom(100'000, 50'000) == 149033233); +} |