Modint
(Math/modint.hpp)

• View this file on GitHub
• Last update: 2024-04-26 03:18:17+09:00
• Include: #include "Math/modint.hpp"

Required by

• Arbitrary Mod Convolution (Convolution/arbitrary.hpp)
• Big Integer(Float) (Math/bigint.hpp)

Verified with

• Verify/LC_bernoulli_number.test.cpp
• Verify/LC_bitwise_and_convolution.test.cpp
• Verify/LC_bitwise_xor_convolution.test.cpp
• Verify/LC_convolution_mod.test.cpp
• Verify/LC_convolution_mod_1000000007.test.cpp
• Verify/LC_convolution_mod_2.test.cpp
• Verify/LC_deque_operate_all_composite.test.cpp
• Verify/LC_dynamic_tree_vertex_set_path_composite.test.cpp
• Verify/LC_enumerate_cliques.test.cpp
• Verify/LC_exp_of_formal_power_series.test.cpp
• Verify/LC_find_linear_recurrence.test.cpp
• Verify/LC_gcd_convolution.test.cpp
• Verify/LC_hafnian_of_matrix.test.cpp
• Verify/LC_inv_of_formal_power_series.test.cpp
• Verify/LC_kth_term_of_linearly_recurrent_sequence.test.cpp
• Verify/LC_lcm_convolution.test.cpp
• Verify/LC_log_of_formal_power_series.test.cpp
• Verify/LC_many_factorials.test.cpp
• Verify/LC_matrix_det.test.cpp
• Verify/LC_matrix_product.test.cpp
• Verify/LC_multipoint_evaluation.test.cpp
• Verify/LC_multivariate_convolution.test.cpp
• Verify/LC_multivariate_convolution_cyclic.test.cpp
• Verify/LC_partition_function.test.cpp
• Verify/LC_point_set_range_composite.test.cpp
• Verify/LC_point_set_range_sort_range_composite.test.cpp
• Verify/LC_polynomial_interpolation.test.cpp
• Verify/LC_polynomial_taylor_shift.test.cpp
• Verify/LC_pow_of_formal_power_series.test.cpp
• Verify/LC_product_of_polynomial_sequence.test.cpp
• Verify/LC_queue_operate_all_composite.test.cpp
• Verify/LC_range_affine_range_sum.test.cpp
• Verify/LC_shift_of_sampling_points_of_polynomial.test.cpp
• Verify/LC_sparse_matrix_det.test.cpp
• Verify/LC_static_rectangle_add_rectangle_sum.test.cpp
• Verify/LC_stirling_number_of_the_first_kind.test.cpp
• Verify/LC_stirling_number_of_the_second_kind.test.cpp
• Verify/LC_subset_convolution.test.cpp
• Verify/LC_sum_of_exponential_times_polynomial.test.cpp
• Verify/LC_sum_of_exponential_times_polynomial_limit.test.cpp
• Verify/LC_sum_of_totient_function.test.cpp
• Verify/LC_system_of_linear_equations.test.cpp
• Verify/LC_vertex_set_path_composite.test.cpp
• Verify/YUKI_1080.test.cpp
• Verify/YUKI_1112.test.cpp
• Verify/YUKI_1781.test.cpp
• Verify/YUKI_2097.test.cpp
• Verify/YUKI_310.test.cpp

Code

#pragma once

template <unsigned mod = 1000000007> struct fp {
    unsigned v;
    static constexpr int get_mod() {
        return mod;
    }
    constexpr unsigned inv() const {
        assert(v != 0);
        int x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
        while (y > 0) {
            t = x / y;
            x -= t * y, p -= t * q;
            tmp = x, x = y, y = tmp;
            tmp = p, p = q, q = tmp;
        }
        if (p < 0)
            p += mod;
        return p;
    }
    constexpr fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    fp operator-() const {
        return fp() - *this;
    }
    fp pow(ull t) {
        fp res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    fp &operator+=(const fp &x) {
        if ((v += x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator-=(const fp &x) {
        if ((v += mod - x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator*=(const fp &x) {
        v = ull(v) * x.v % mod;
        return *this;
    }
    fp &operator/=(const fp &x) {
        v = ull(v) * x.inv() % mod;
        return *this;
    }
    fp operator+(const fp &x) const {
        return fp(*this) += x;
    }
    fp operator-(const fp &x) const {
        return fp(*this) -= x;
    }
    fp operator*(const fp &x) const {
        return fp(*this) *= x;
    }
    fp operator/(const fp &x) const {
        return fp(*this) /= x;
    }
    bool operator==(const fp &x) const {
        return v == x.v;
    }
    bool operator!=(const fp &x) const {
        return v != x.v;
    }
    friend istream &operator>>(istream &is, fp &x) {
        return is >> x.v;
    }
    friend ostream &operator<<(ostream &os, const fp &x) {
        return os << x.v;
    }
};

template <unsigned mod> void rd(fp<mod> &x) {
    fastio::rd(x.v);
}
template <unsigned mod> void wt(fp<mod> x) {
    fastio::wt(x.v);
}

template <typename T> T Inv(ll n) {
    static const int md = T::get_mod();
    static vector<T> buf({0, 1});
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static const int md = T::get_mod();
    static vector<T> buf({1, 1}), ibuf({1, 1});
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r, inv);
}

/**
 * @brief Modint
 */

#line 2 "Math/modint.hpp"

template <unsigned mod = 1000000007> struct fp {
    unsigned v;
    static constexpr int get_mod() {
        return mod;
    }
    constexpr unsigned inv() const {
        assert(v != 0);
        int x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
        while (y > 0) {
            t = x / y;
            x -= t * y, p -= t * q;
            tmp = x, x = y, y = tmp;
            tmp = p, p = q, q = tmp;
        }
        if (p < 0)
            p += mod;
        return p;
    }
    constexpr fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
    fp operator-() const {
        return fp() - *this;
    }
    fp pow(ull t) {
        fp res = 1, b = *this;
        while (t) {
            if (t & 1)
                res *= b;
            b *= b;
            t >>= 1;
        }
        return res;
    }
    fp &operator+=(const fp &x) {
        if ((v += x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator-=(const fp &x) {
        if ((v += mod - x.v) >= mod)
            v -= mod;
        return *this;
    }
    fp &operator*=(const fp &x) {
        v = ull(v) * x.v % mod;
        return *this;
    }
    fp &operator/=(const fp &x) {
        v = ull(v) * x.inv() % mod;
        return *this;
    }
    fp operator+(const fp &x) const {
        return fp(*this) += x;
    }
    fp operator-(const fp &x) const {
        return fp(*this) -= x;
    }
    fp operator*(const fp &x) const {
        return fp(*this) *= x;
    }
    fp operator/(const fp &x) const {
        return fp(*this) /= x;
    }
    bool operator==(const fp &x) const {
        return v == x.v;
    }
    bool operator!=(const fp &x) const {
        return v != x.v;
    }
    friend istream &operator>>(istream &is, fp &x) {
        return is >> x.v;
    }
    friend ostream &operator<<(ostream &os, const fp &x) {
        return os << x.v;
    }
};

template <unsigned mod> void rd(fp<mod> &x) {
    fastio::rd(x.v);
}
template <unsigned mod> void wt(fp<mod> x) {
    fastio::wt(x.v);
}

template <typename T> T Inv(ll n) {
    static const int md = T::get_mod();
    static vector<T> buf({0, 1});
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static const int md = T::get_mod();
    static vector<T> buf({1, 1}), ibuf({1, 1});
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r, inv);
}

/**
 * @brief Modint
 */

Back to top page