library/mod/MintUtility.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/mod/MintUtility.hpp"

Depends on

• build/pch/stdc++.hpp

Verified with

• test/yukicoder/117.test.cpp

Code

template <typename MINT> class MintUtility {
    std::vector<MINT> fact_ = {MINT::raw(1)};
    std::vector<MINT> inv_fact_{MINT::raw(1)};
    int S = 1; // 今のサイズ

    void extend(const int n) {
        if (n < S)
            return;
        const int preS = S;
        do {
            S <<= 1;
        } while (S <= n);

        fact_.resize(S);
        for (int i = preS; i < S; i++)
            fact_[i] = fact_[i - 1] * MINT::raw(i);

        inv_fact_.resize(S);
        inv_fact_.back() = fact_.back().inv();
        for (int i = S - 1; i > preS; i--)
            inv_fact_[i - 1] = inv_fact_[i] * MINT::raw(i);
    }

  public:
    MINT fact(const int n) {
        assert(n >= 0);
        extend(n);
        return fact_[n];
    }
    MINT inv_fact(const int n) {
        assert(n >= 0);
        extend(n);
        return inv_fact_[n];
    }
    MINT nCk(const int n, const int k) {
        if (k < 0 || n < k)
            return MINT::raw(0);
        extend(n);
        return fact_[n] * inv_fact_[k] * inv_fact_[n - k];
    }
    MINT nPk(const int n, const int k) {
        if (k < 0 || n < k)
            return MINT::raw(0);
        extend(n);
        return fact_[n] * inv_fact_[n - k];
    }
    MINT nHk(const int n, const int k) {
        return (n == 0 and k == 0 ? 1 : nCk(n + k - 1, k));
    }
};

#line 1 "library/mod/MintUtility.hpp"
template <typename MINT> class MintUtility {
    std::vector<MINT> fact_ = {MINT::raw(1)};
    std::vector<MINT> inv_fact_{MINT::raw(1)};
    int S = 1; // 今のサイズ

    void extend(const int n) {
        if (n < S)
            return;
        const int preS = S;
        do {
            S <<= 1;
        } while (S <= n);

        fact_.resize(S);
        for (int i = preS; i < S; i++)
            fact_[i] = fact_[i - 1] * MINT::raw(i);

        inv_fact_.resize(S);
        inv_fact_.back() = fact_.back().inv();
        for (int i = S - 1; i > preS; i--)
            inv_fact_[i - 1] = inv_fact_[i] * MINT::raw(i);
    }

  public:
    MINT fact(const int n) {
        assert(n >= 0);
        extend(n);
        return fact_[n];
    }
    MINT inv_fact(const int n) {
        assert(n >= 0);
        extend(n);
        return inv_fact_[n];
    }
    MINT nCk(const int n, const int k) {
        if (k < 0 || n < k)
            return MINT::raw(0);
        extend(n);
        return fact_[n] * inv_fact_[k] * inv_fact_[n - k];
    }
    MINT nPk(const int n, const int k) {
        if (k < 0 || n < k)
            return MINT::raw(0);
        extend(n);
        return fact_[n] * inv_fact_[n - k];
    }
    MINT nHk(const int n, const int k) {
        return (n == 0 and k == 0 ? 1 : nCk(n + k - 1, k));
    }
};

Back to top page