test/EnumerativeCombinatorics/combination_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp

View this file on GitHub
Last update: 2026-05-17 15:50:36+09:00
Problem: https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

Depends on

組合せ・順列・重複組合せ (素数 mod) (EnumerativeCombinatorics/combination_prime_mod.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

#include "EnumerativeCombinatorics/combination_prime_mod.hpp"
#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;

using mint = atcoder::modint;

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

    mint::set_mod(m);

    combinatorics<atcoder::modint> comb(min(m, 10000000) - 1);

    for (int i = 0; i < T; i++)
    {
        int n, k;
        cin >> n >> k;
        cout << comb(n, k).val() << endl;
    }

    return 0;
}

#line 1 "test/EnumerativeCombinatorics/combination_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

#line 1 "EnumerativeCombinatorics/combination_prime_mod.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class mint>
class combinatorics
{
private:
    int max_n;
    vector<mint> fact, ifact;

public:
    combinatorics(int n) : max_n(n), fact(n + 1), ifact(n + 1)
    {
        assert(n < mint::mod());

        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;

        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k)
    {
        return C(n, k);
    }

    // nCr
    mint C(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[r] * ifact[n - r];
    }

    // nPr
    mint P(int n, int r)
    {
        if (n < 0 || r < 0 || r > n)
            return 0;
        assert(n <= max_n);

        return fact[n] * ifact[n - r];
    }

    // nHr
    mint H(int n, int r)
    {
        if (n < 0 || r < 0)
            return 0;

        if (n == 0)
            return r == 0 ? 1 : 0;

        return C(n + r - 1, r);
    }
};
#line 4 "test/EnumerativeCombinatorics/combination_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp"
#include <atcoder/modint>
#line 6 "test/EnumerativeCombinatorics/combination_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp"

using namespace std;

using mint = atcoder::modint;

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

    mint::set_mod(m);

    combinatorics<atcoder::modint> comb(min(m, 10000000) - 1);

    for (int i = 0; i < T; i++)
    {
        int n, k;
        cin >> n >> k;
        cout << comb(n, k).val() << endl;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	3 ms	4 MB
g++	example_01	AC	2 ms	3 MB
g++	large_random_00	AC	2201 ms	81 MB
g++	large_random_01	AC	1777 ms	81 MB
g++	large_random_02	AC	2028 ms	81 MB
g++	med_random_00	AC	1910 ms	6 MB
g++	med_random_01	AC	1733 ms	6 MB
g++	med_random_02	AC	2258 ms	8 MB
g++	mod1000000007_00	AC	2219 ms	81 MB
g++	mod1000000007_01	AC	1743 ms	81 MB
g++	mod2_00	AC	1402 ms	3 MB
g++	mod2_01	AC	1501 ms	3 MB
g++	mod3_00	AC	1343 ms	3 MB
g++	mod3_01	AC	1373 ms	3 MB
g++	mod998244353_00	AC	1912 ms	81 MB
g++	mod998244353_01	AC	1929 ms	81 MB
g++	mod998244353_maxi_00	AC	1898 ms	81 MB
g++	small_random_00	AC	1415 ms	3 MB
g++	small_random_01	AC	1394 ms	3 MB
g++	small_random_02	AC	1435 ms	3 MB