test/math/binomial.test.cpp

View this file on GitHub
Last update: 2025-11-15 20:52:05+09:00
Problem: https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

Depends on

Required by

test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod"

#include "../../math/binomial.hpp"
#include "../../math/dynamic_mod_int.hpp"
#include "../../template/template.hpp"

int main() {
    int T, M;
    cin >> T >> M;

    DynamicModInt::set_mod(M);
    Binomial<DynamicModInt> bin(min(M - 1, 10000000));

    while (T--) {
        int n, k;
        cin >> n >> k;

        cout << bin.c(n, k).val() << LF;
    }

    return 0;
}

#line 1 "test/math/binomial.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod"

#line 2 "math/binomial.hpp"

#line 2 "template/template.hpp"

/**
 * @author ku_senjan
 * @title 提出用テンプレート
 * @see https://github.com/kogetsu0728/ku-library
 */

#line 2 "template/constant.hpp"

#line 2 "template/include.hpp"

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
#line 2 "template/type_alias.hpp"

#line 4 "template/type_alias.hpp"

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

using ld = long double;

template <class T, bool REVERSE = false>
using heap = priority_queue<T, vector<T>, conditional_t<REVERSE, greater<T>, less<T>>>;
#line 5 "template/constant.hpp"

template <class T>
inline constexpr T INF = numeric_limits<T>::max() / 2;

inline constexpr array<int, 4> DY4 = {0, -1, 0, 1};
inline constexpr array<int, 4> DX4 = {1, 0, -1, 0};
inline constexpr array<int, 8> DY8 = {0, -1, -1, -1, 0, 1, 1, 1};
inline constexpr array<int, 8> DX8 = {1, 1, 0, -1, -1, -1, 0, 1};

inline constexpr char LF = '\n';
#line 2 "template/macro.hpp"

#line 5 "template/macro.hpp"

/**
 * @see https://trap.jp/post/1224/
 */

#ifdef LOCAL
inline constexpr bool IS_LOCAL = true;
#else
inline constexpr bool IS_LOCAL = false;
#endif

#define IF_LOCAL if constexpr (IS_LOCAL)

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define overload4(a, b, c, d, e, ...) e

#define rep1(i, a) for (ll i = 0; (i) < (ll)(a); ++(i))
#define rep2(i, a, b) for (ll i = (ll)(a); (i) < (ll)(b); ++(i))
#define rep3(i, a, b, c) for (ll i = (ll)(a); (i) < (ll)(b); (i) += (ll)(c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(i, a) for (ll i = (ll)(a); (i) >= 0; --(i))
#define rrep2(i, a, b) for (ll i = (ll)(a); (i) >= (ll)(b); --(i))
#define rrep3(i, a, b, c) for (ll i = (ll)(a); (i) >= (ll)(b); (i) -= (ll)(c))
#define rrep(...) overload4(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#line 13 "template/template.hpp"

#line 2 "utility/choose_min_max.hpp"

/**
 * @title Choose Minimum / Maximum
 */

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }

    return false;
}

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}
#line 2 "utility/set_io.hpp"

#line 4 "utility/set_io.hpp"

void set_io(int d = 16) {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(d);

    return;
}
#line 4 "math/binomial.hpp"

/**
 * @brief Binomial (二項係数)
 * @note 参考: https://blog.hamayanhamayan.com/entry/2018/06/06/210256
 */
template <class T>
class Binomial {
  private:
    int n;
    vector<T> fact, ifact;

  public:
    Binomial() : Binomial(0) {}
    Binomial(int _n) : n(_n), fact(_n + 1), ifact(_n + 1) {
        assert(0 <= _n);

        fact[0] = T(1);
        rep (i, 0, n) {
            fact[i + 1] = fact[i] * T(i + 1);
        }

        ifact[n] = T(1) / fact[n];
        rrep (i, n, 1) {
            ifact[i - 1] = ifact[i] * T(i);
        }
    }

    //! 順列
    T p(int a, int b) const {
        if (b < 0 || a < b) {
            return T(0);
        }

        assert(0 <= a && a <= n);
        assert(0 <= a - b && a - b <= n);

        return fact[a] * ifact[a - b];
    }

    //! 組合せ
    T c(int a, int b) const {
        if (b < 0 || a < b) {
            return T(0);
        }

        assert(0 <= b && b <= n);

        return p(a, b) * ifact[b];
    }

    //! 重複組合せ
    T h(int a, int b) const {
        if (a == 0 && b == 0) {
            return T(1);
        }

        if (a <= 0 || b < 0) {
            return T(0);
        }

        return c(a + b - 1, b);
    }
};
#line 2 "math/dynamic_mod_int.hpp"

#line 4 "math/dynamic_mod_int.hpp"

/**
 * @brief Dynamic Mod Int
 * @note 仮実装
 */
class DynamicModInt {
  private:
    int v;
    static int m;

  public:
    DynamicModInt() : v(0) {}
    DynamicModInt(ll _v) : v(int(((_v % m) + m) % m)) {}

    static void set_mod(int _m) {
        m = _m;
        assert(m <= INT_MAX / 2);

        return;
    }

    static DynamicModInt raw(int _v) {
        DynamicModInt res;
        res.v = _v;

        return res;
    }

    static int mod() { return m; }
    int val() const { return v; }

    friend bool operator==(const DynamicModInt& lhs, const DynamicModInt& rhs) {
        return lhs.v == rhs.v;
    }

    friend bool operator!=(const DynamicModInt& lhs, const DynamicModInt& rhs) {
        return !(lhs == rhs);
    }

    DynamicModInt& operator+=(const DynamicModInt& rhs) {
        v += rhs.v;
        if (m <= v) {
            v -= m;
        }

        return *this;
    }

    DynamicModInt& operator-=(const DynamicModInt& rhs) {
        if (v < rhs.v) {
            v += m;
        }
        v -= rhs.v;

        return *this;
    }

    DynamicModInt& operator*=(const DynamicModInt& rhs) {
        v = (ull(v) * rhs.val()) % m;

        return *this;
    }

    DynamicModInt& operator/=(const DynamicModInt& rhs) {
        assert(rhs.v != 0);

        return *this *= rhs.inv();
    }

    friend DynamicModInt operator+(const DynamicModInt& lhs, const DynamicModInt& rhs) {
        return DynamicModInt(lhs) += rhs;
    }

    friend DynamicModInt operator-(const DynamicModInt& lhs, const DynamicModInt& rhs) {
        return DynamicModInt(lhs) -= rhs;
    }

    friend DynamicModInt operator*(const DynamicModInt& lhs, const DynamicModInt& rhs) {
        return DynamicModInt(lhs) *= rhs;
    }

    friend DynamicModInt operator/(const DynamicModInt& lhs, const DynamicModInt& rhs) {
        return DynamicModInt(lhs) /= rhs;
    }

    DynamicModInt pow(ll y) const {
        DynamicModInt res = raw(1);
        DynamicModInt x = *this;

        while (0 < y) {
            if (y & 1) {
                res *= x;
            }

            x *= x;
            y >>= 1;
        }

        return res;
    }

    DynamicModInt inv() const { return pow(m - 2); }
};

int DynamicModInt::m = 998244353;
#line 6 "test/math/binomial.test.cpp"

int main() {
    int T, M;
    cin >> T >> M;

    DynamicModInt::set_mod(M);
    Binomial<DynamicModInt> bin(min(M - 1, 10000000));

    while (T--) {
        int n, k;
        cin >> n >> k;

        cout << bin.c(n, k).val() << LF;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	large_random_00	AC	1614 ms	81 MB
g++	large_random_01	AC	1555 ms	81 MB
g++	large_random_02	AC	1571 ms	81 MB
g++	med_random_00	AC	1305 ms	6 MB
g++	med_random_01	AC	1275 ms	6 MB
g++	med_random_02	AC	1336 ms	8 MB
g++	mod1000000007_00	AC	1517 ms	81 MB
g++	mod1000000007_01	AC	1530 ms	81 MB
g++	mod2_00	AC	1042 ms	3 MB
g++	mod2_01	AC	1030 ms	4 MB
g++	mod3_00	AC	1116 ms	4 MB
g++	mod3_01	AC	1077 ms	4 MB
g++	mod998244353_00	AC	1597 ms	81 MB
g++	mod998244353_01	AC	1583 ms	81 MB
g++	mod998244353_maxi_00	AC	1606 ms	81 MB
g++	small_random_00	AC	1080 ms	4 MB
g++	small_random_01	AC	1085 ms	3 MB
g++	small_random_02	AC	1115 ms	4 MB