src/Math/Combination.hpp

• View this file on GitHub
• Last update: 2020-04-01 18:54:36+09:00
• Include: #include "src/Math/Combination.hpp"

Verified with

• test/aoj/DPL_5_B.test.cpp
• test/aoj/DPL_5_D.test.cpp
• test/aoj/DPL_5_D_runtime.test.cpp
• test/aoj/DPL_5_E.test.cpp
• test/aoj/DPL_5_F.test.cpp

Code

template <class T> struct Combination {
    std::vector<T> fact, fact_inv;
    Combination(int n = 1000003) : fact(n + 1, 1), fact_inv(n + 1) {
        for (int i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1);
        fact_inv[n] = (T)1 / fact[n];
        for (int i = n - 1; i >= 0; i--) fact_inv[i] = fact_inv[i + 1] * (i + 1);
        // for (int i = 0; i < n + 1; i++) assert(fact[i] * fact_inv[i] == 1);
    }
    T operator()(int n, int r) { return fact[n] * fact_inv[r] * fact_inv[n - r]; }
};

#line 1 "src/Math/Combination.hpp"
template <class T> struct Combination {
    std::vector<T> fact, fact_inv;
    Combination(int n = 1000003) : fact(n + 1, 1), fact_inv(n + 1) {
        for (int i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1);
        fact_inv[n] = (T)1 / fact[n];
        for (int i = n - 1; i >= 0; i--) fact_inv[i] = fact_inv[i + 1] * (i + 1);
        // for (int i = 0; i < n + 1; i++) assert(fact[i] * fact_inv[i] == 1);
    }
    T operator()(int n, int r) { return fact[n] * fact_inv[r] * fact_inv[n - r]; }
};

Back to top page