test/EnumerativeCombinatorics/binomial_coefficient_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp

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

Depends on

二項係数 (素数 mod) (EnumerativeCombinatorics/binomial_coefficient_prime_mod.hpp)

Code

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

#include "EnumerativeCombinatorics/binomial_coefficient_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);

    combination<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/binomial_coefficient_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

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

template <class mint>
class combination
{
private:
    vector<mint> fact, ifact;

public:
    combination(int 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)
    {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};
#line 4 "test/EnumerativeCombinatorics/binomial_coefficient_prime_mod/yosupo-binomial_coefficient_prime_mod.cpp"
#include <atcoder/modint>
#line 6 "test/EnumerativeCombinatorics/binomial_coefficient_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);

    combination<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	5 ms	4 MB
g++	example_01	AC	4 ms	3 MB
g++	large_random_00	AC	1536 ms	81 MB
g++	large_random_01	AC	1499 ms	81 MB
g++	large_random_02	AC	1573 ms	81 MB
g++	med_random_00	AC	1411 ms	6 MB
g++	med_random_01	AC	1500 ms	6 MB
g++	med_random_02	AC	1332 ms	8 MB
g++	mod1000000007_00	AC	1547 ms	81 MB
g++	mod1000000007_01	AC	1537 ms	81 MB
g++	mod2_00	AC	1205 ms	3 MB
g++	mod2_01	AC	1085 ms	3 MB
g++	mod3_00	AC	1169 ms	3 MB
g++	mod3_01	AC	1084 ms	3 MB
g++	mod998244353_00	AC	1584 ms	81 MB
g++	mod998244353_01	AC	1572 ms	81 MB
g++	mod998244353_maxi_00	AC	1670 ms	81 MB
g++	small_random_00	AC	1115 ms	3 MB
g++	small_random_01	AC	1099 ms	3 MB
g++	small_random_02	AC	1090 ms	3 MB