mkreem_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub mkr33m/mkreem_library

:warning: a の mod m における逆元 x を求める
(Math/BinomMod_ll.hpp)

Depends on

Code

#ifndef binom_mod_ll_HPP
#define binom_mod_ll_HPP

#include <vector>
#include <cassert>

#include "../Others/macros.hpp"
#include "extended_gcd.hpp"

struct BinomModLL {
private:
    int MAX_N;
    ll MOD;
    std::vector<ll> factorial, factorial_inv;

    /**
     * @brief a の mod m における逆元 x を求める
     * a*x == 1 を満たす x を求めたいということは、a*x + b*y == 1 を満たす x を求めたいということ
     */
    ll mod_inverse(ll a, ll m) {
        ll x, y;
        ll g = extended_gcd(a, m, x, y);
        assert(g == 1);
        return (x % m + m) % m;
    }

public:
    BinomModLL(int MAX_N = 10000000, ll MOD = 998244353) : MAX_N(MAX_N), MOD(MOD) {
        factorial[0] = 1;
        for (int i = 1; i <= MAX_N; i++) {
            factorial[i] = factorial[i - 1] * i % MOD;
        }
        factorial_inv[MAX_N] = mod_inverse(factorial[MAX_N], MOD);
        for (int i = MAX_N - 1; i >= 0; i--) {
            /*
            ((i+1)!)^(-1) ≡ (i+1)^(-1) * (i!)^(-1)
            より、
            (i!)^(-1) == ((i+1)!)^(-1) * (i+1)
            */
            factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % MOD;
        }
    }

    ll val(int N, int K) {
        if (N < K || N < 0 || K < 0) {
            return 0;
        }
        return factorial[N] * (factorial_inv[K] * factorial_inv[N - K] % MOD) % MOD;
    }
};

#endif //binom_mod_ll_HPP
#line 1 "Math/BinomMod_ll.hpp"



#include <vector>
#include <cassert>

#line 1 "Others/macros.hpp"



#line 5 "Others/macros.hpp"
#include <queue>
#include <cmath>

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define REF const auto&
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define BIT(i) (1LL << (i))
#define tbit(n, k) ((n >> k) & 1) // nの(上から)kビット目
#define bit(n, k) (n & (1LL << (k))) // nの(下から)kビット目
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define einr(l, x, r) (l <= x && x <= r)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define repl(i, a, b) for(long long i = (a); i < (b); i++)
#define erepl(i, a, b) for(long long i = (a); i <= (b); i++)
#define rrepl(i, a, b) for(long long i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR_subset(sub, bit) for (ll sub = (bit); sub >= 0; sub = (sub == 0 ? -1 : (sub - 1) & (bit)))
#define UNIQUE(v) (std::sort(all(v)), (v).erase(std::unique(all(v)), (v).end()))
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define VC(name, type, ...) vector<type> name(__VA_ARGS__)
#define VVC(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define VVVC(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define VVVVC(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define VVVVVC(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using maxpq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if (a < b) { a = b; return 1; }
    return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if (a > b) { a = b; return 1; }
    return 0;
}

const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

bool out_of_grid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}


#line 1 "Math/extended_gcd.hpp"



/**
 * @brief a * x + b * y == gcd(a, b)を満たす x, y を見つける
 * @return gcd(a, b)
 * x が a の逆元に相当
 */
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    /*
    a * x0 + b * y0 == gcd(a, b)
    ↓ a = q * b + r(ユークリッドの互除法)
    -> b * x1 + r * y1 == gcd(a, b)
    -> ...
    -> gcd(a, b) * xn + 0 * yn == gcd(a, b)
    */
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long prev_x, prev_y;
    long long gcd = extended_gcd(b, a % b, prev_x, prev_y);
    // 帰りがけに係数を更新
    x = prev_y;
    y = prev_x - (a / b) * prev_y;
    
    return gcd;
}


#line 9 "Math/BinomMod_ll.hpp"

struct BinomModLL {
private:
    int MAX_N;
    ll MOD;
    std::vector<ll> factorial, factorial_inv;

    /**
     * @brief a の mod m における逆元 x を求める
     * a*x == 1 を満たす x を求めたいということは、a*x + b*y == 1 を満たす x を求めたいということ
     */
    ll mod_inverse(ll a, ll m) {
        ll x, y;
        ll g = extended_gcd(a, m, x, y);
        assert(g == 1);
        return (x % m + m) % m;
    }

public:
    BinomModLL(int MAX_N = 10000000, ll MOD = 998244353) : MAX_N(MAX_N), MOD(MOD) {
        factorial[0] = 1;
        for (int i = 1; i <= MAX_N; i++) {
            factorial[i] = factorial[i - 1] * i % MOD;
        }
        factorial_inv[MAX_N] = mod_inverse(factorial[MAX_N], MOD);
        for (int i = MAX_N - 1; i >= 0; i--) {
            /*
            ((i+1)!)^(-1) ≡ (i+1)^(-1) * (i!)^(-1)
            より、
            (i!)^(-1) == ((i+1)!)^(-1) * (i+1)
            */
            factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % MOD;
        }
    }

    ll val(int N, int K) {
        if (N < K || N < 0 || K < 0) {
            return 0;
        }
        return factorial[N] * (factorial_inv[K] * factorial_inv[N - K] % MOD) % MOD;
    }
};
Back to top page