math/combination.cpp

Back to top page

• category: math
• View this file on GitHub
  • Last commit date: 2020-09-06 22:27:11+09:00

Code

// require modint
struct combination {
    vector<mint> fact, ifact;
    combination(const int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(const int n, const int k) {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
} comb(100005);

#line 1 "math/combination.cpp"
// require modint
struct combination {
    vector<mint> fact, ifact;
    combination(const int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(const int n, const int k) {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
} comb(100005);

Back to top page