verify/math/combo.test.cpp

• View this file on GitHub
• Last update: 2024-12-11 17:30:10-05:00
• Problem: https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

Depends on

• algo/common.h
• algo/math/combo.h
• algo/math/common.h
• algo/math/modint.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod"
#define ALGO_MAXN 1e7
#include "algo/common.h"

/* #include */
#include "algo/math/combo.h"
#include "algo/math/modint.h"

using namespace std;
using namespace algo;
using namespace math;

void solve() {
    int n, k;
    cin >> n >> k;
    cout << cmb<mint>(n, k) << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t, m;
    cin >> t >> m;
    mint::set_mod(m);
    while (t--)
        solve();
}

#line 1 "verify/math/combo.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod"
#define ALGO_MAXN 1e7
#line 2 "algo/common.h"
#ifndef PREPROCESS
#include <bits/stdc++.h>
#endif

namespace algo {}

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#line 4 "verify/math/combo.test.cpp"

/* #include */
#line 3 "algo/math/common.h"

#ifdef ALGO_MAXN
const int MAXN = ALGO_MAXN;
#else
const int MAXN = 1 << 19;
#endif

namespace algo::math {

constexpr int64_t safe_mod(int64_t x, int64_t m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

// Returns (x ** n) % m
constexpr int64_t pow_mod_constexpr(int64_t x, int64_t n, int m) {
    assert(0 <= n);
    assert(1 <= m);
    if (m == 1) return 0;
    uint _m = (uint)(m);
    uint64_t r = 1;
    uint64_t y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

struct barrett {
    explicit barrett(uint64_t _m) : m(_m), im(-1ULL / _m) {
        assert(1 <= _m);
    }
    uint64_t mod() {
        return m;
    };
    uint64_t reduce(uint64_t a) {
        uint64_t q = (uint64_t)((__uint128_t(im) * a) >> 64);
        uint64_t r = a - q * m;
        return r - (r >= m) * m;
    }

private:
    uint64_t m, im;
};

constexpr int64_t c_div(int64_t a, int64_t b) {
    return a / b + ((a ^ b) > 0 && a % b);
}
constexpr int64_t f_div(int64_t a, int64_t b) {
    return a / b - ((a ^ b) < 0 && a % b);
}

auto bpow(auto const &x, auto n, auto const &one, auto op) {
    if (n == 0) {
        return one;
    } else {
        auto t = bpow(x, n / 2, one, op);
        t = op(t, t);
        if (n % 2) {
            t = op(t, x);
        }
        return t;
    }
}
auto bpow(auto x, auto n, auto ans) {
    return bpow(x, n, ans, std::multiplies{});
}
template <typename T>
T bpow(T const &x, auto n) {
    return bpow(x, n, T(1));
}

// Returns a pair(g, x) s.t. g = gcd(a, n), xa = g (mod n), 0 <= x < n/g
// If r > 1 then a is not invertible mod n
constexpr std::pair<int64_t, int64_t> inv_gcd(int64_t a, int64_t n) {
    a = safe_mod(a, n);
    if (a == 0) return {n, 0};

    int64_t t = 0, newt = 1;
    int64_t r = n, newr = a;

    while (newr) {
        int64_t quotient = r / newr;
        r -= newr * quotient;
        t -= newt * quotient;

        std::swap(r, newr);
        std::swap(t, newt);
    }
    if (t < 0) t += n / r;
    return {r, t};
}

} // namespace algo::math
#line 4 "algo/math/combo.h"

namespace algo::math {

template <typename T>
T fact(int n) {
    static std::vector<T> F(MAXN);
    static bool init = false;
    if (!init) {
        F[0] = T(1);
        for (int i = 1; i < MAXN; i++) {
            F[i] = F[i - 1] * T(i);
        }
        init = true;
    }
    return F[n];
}
template <typename T>
T inv_fact(int n) {
    static std::vector<T> F(MAXN);
    static bool init = false;
    if (!init) {
        int t = std::min(T::mod(), MAXN) - 1;
        F[t] = T(1) / fact<T>(t);
        for (int i = t - 1; i >= 0; i--) {
            F[i] = F[i + 1] * T(i + 1);
        }
        init = true;
    }
    return F[n];
}
template <typename T>
T cmb(int n, int r) {
    assert(n < MAXN);
    if (r < 0 || r > n) {
        return T(0);
    } else {
        return fact<T>(n) * inv_fact<T>(r) * inv_fact<T>(n - r);
    }
}
template <typename T>
T perm(int n, int r) {
    assert(n < MAXN);
    if (r < 0 || r > n) {
        return T(0);
    } else {
        return fact<T>(n) * inv_fact<T>(n - r);
    }
}

} // namespace algo::math
#line 4 "algo/math/modint.h"

namespace algo::math {

template <int id>
struct modint {
    static int mod() {
        return bt.mod();
    }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = barrett(m);
    }
    auto static with_mod(int tmp, auto callback) {
        struct scoped {
            int prev = mod();
            ~scoped() {
                set_mod(prev);
            }
        } _;
        set_mod(tmp);
        return callback();
    }
    modint() : v(0) {
    }
    modint(int64_t _v) {
        v = (-mod() < _v && _v < mod()) ? _v : _v % mod();
        if (v < 0) v += mod();
    }
    modint &operator+=(const modint &other) {
        v += other.v;
        if (v >= mod()) v -= mod();
        return *this;
    }
    modint &operator-=(const modint &other) {
        v -= other.v;
        if (v < 0) v += mod();
        return *this;
    }
    modint &operator*=(const modint &other) {
        v = bt.reduce((int64_t)v * other.v);
        return *this;
    }
    modint &operator/=(const modint &other) {
        return *this = *this * other.inv();
    }
    int &operator++() {
        v++;
        if (v == mod()) v = 0;
        return *this;
    }
    modint &operator--() {
        if (v == 0) v = mod();
        v--;
        return *this;
    }
    modint operator++(int) {
        modint result = *this;
        ++*this;
        return result;
    }
    modint operator--(int) {
        modint result = *this;
        --*this;
        return result;
    }
    friend modint operator+(modint a, const modint &b) {
        return a += b;
    }
    friend modint operator-(modint a, const modint &b) {
        return a -= b;
    }
    friend modint operator*(modint a, const modint &b) {
        return a *= b;
    }
    friend modint operator/(modint a, const modint &b) {
        return a /= b;
    }
    friend modint operator-(modint a) {
        return 0 - a;
    }
    modint inv() const {
        auto eg = inv_gcd(v, mod());
        assert(eg.first == 1);
        return eg.second;
    }
    friend bool operator==(const modint &a, const modint &b) {
        return a.v == b.v;
    }
    friend bool operator!=(const modint &a, const modint &b) {
        return !(a == b);
    }
    explicit operator int() const {
        return v;
    }
    friend std::ostream &operator<<(std::ostream &os, const modint &a) {
        return os << a.v;
    }
    friend std::istream &operator>>(std::istream &is, modint &a) {
        is >> a.v;
        a.v = (mod() < a.v && a.v < mod()) ? a.v : a.v % mod();
        if (a.v < 0) a.v += mod();
        return is;
    }

private:
    int v;
    static barrett bt;
};
template <int id>
barrett modint<id>::bt(998244353);

using mint = modint<-1>;

} // namespace algo::math
#line 8 "verify/math/combo.test.cpp"

using namespace std;
using namespace algo;
using namespace math;

void solve() {
    int n, k;
    cin >> n >> k;
    cout << cmb<mint>(n, k) << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t, m;
    cin >> t >> m;
    mint::set_mod(m);
    while (t--)
        solve();
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	64 ms	81 MB
g++	example_01	AC	62 ms	81 MB
g++	large_random_00	AC	319 ms	81 MB
g++	large_random_01	AC	328 ms	81 MB
g++	large_random_02	AC	317 ms	81 MB
g++	med_random_00	AC	217 ms	81 MB
g++	med_random_01	AC	224 ms	81 MB
g++	med_random_02	AC	227 ms	81 MB
g++	mod1000000007_00	AC	320 ms	81 MB
g++	mod1000000007_01	AC	322 ms	81 MB
g++	mod2_00	AC	178 ms	81 MB
g++	mod2_01	AC	178 ms	81 MB
g++	mod3_00	AC	176 ms	81 MB
g++	mod3_01	AC	176 ms	81 MB
g++	mod998244353_00	AC	326 ms	81 MB
g++	mod998244353_01	AC	326 ms	81 MB
g++	mod998244353_maxi_00	AC	387 ms	81 MB
g++	small_random_00	AC	182 ms	81 MB
g++	small_random_01	AC	182 ms	81 MB
g++	small_random_02	AC	180 ms	81 MB

Back to top page