test/math/binomial_coefficient_prime_mod.test.cpp

• View this file on GitHub
• Last update: 2026-02-06 02:13:39+09:00
• Problem: https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

Depends on

• math/combinatorics.hpp

Code

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

#include "math/combinatorics.hpp"
#include <atcoder/modint>
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    using Z = atcoder::modint;
    Combinatorics<Z> C;
    int T, m;
    std::cin >> T >> m;
    Z::set_mod(m);
    for (auto i = 0; i < T; ++i) {
        int n, k;
        std::cin >> n >> k;
        std::cout << C(n, k).val() << "\n";
    }
}

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

#line 1 "math/combinatorics.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>

template <typename Z> struct Combinatorics {
    static void grow(int n) {
        auto m = int(f_.size());
        if (n < m) {
            return;
        }
        n = std::min<int>(std::bit_ceil(unsigned(n + 1)), Z::mod());
        f_.resize(n);
        finv_.resize(n);
        for (auto i = m; i < n; ++i) {
            f_[i] = f_[i - 1] * Z(i);
        }
        finv_[n - 1] = f_[n - 1].inv();
        for (auto i = n - 1; m < i; --i) {
            finv_[i - 1] = finv_[i] * Z(i);
        }
    }
    static Z f(int n) { // O(1)
        assert(0 <= n);
        grow(n);
        return f_[n];
    }
    static Z finv(int n) { // O(1)
        assert(0 <= n);
        grow(n);
        return finv_[n];
    }
    static Z binom(int n, int k) { // O(1)
        if (0 <= k && k <= n) {
            return f(n) * finv(k) * finv(n - k);
        } else {
            return Z(0);
        }
    }
    static Z binom2(long long n, long long k) { // O(min(k, n - k))
        if (k < 0 || n < k) {
            return Z(0);
        }
        if (n - k < k) {
            return binom2(n, n - k);
        }
        auto ret = finv(int(k));
        for (auto i = 0; i < k; ++i) {
            ret *= Z(n - i);
        }
        return ret;
    }
    Z operator()(int n, int k) { return binom(n, k); }

private:
    inline static std::vector<Z> f_{Z(1)}, finv_{Z(1)};
};


#line 4 "test/math/binomial_coefficient_prime_mod.test.cpp"
#include <atcoder/modint>
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    using Z = atcoder::modint;
    Combinatorics<Z> C;
    int T, m;
    std::cin >> T >> m;
    Z::set_mod(m);
    for (auto i = 0; i < T; ++i) {
        int n, k;
        std::cin >> n >> k;
        std::cout << C(n, k).val() << "\n";
    }
}

Back to top page