verify/yosupo/yosupo_binomial_coefficient_prime_mod.test.cpp

• View this file on GitHub
• Last update: 2024-11-18 13:42:40+09:00
• Problem: https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

Depends on

• math/binomial_coefficient.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../../math/binomial_coefficient.hpp"

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T, m;
    cin >> T >> m;

    vector<int> N(T), K(T);
    int mx = 0;
    for(int i = 0; i < T; i++) {
        cin >> N[i] >> K[i];
        mx = max(mx, N[i]);
    }

    BinomialCoefficient binom(mx, m);
    for(int i = 0; i < T; i++) {
        cout << binom(N[i], K[i]) << "\n";
    }

    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#line 1 "math/binomial_coefficient.hpp"
struct BinomialCoefficient{
    int MOD;
    vector<long long> fact, fact_inv, inv;

    BinomialCoefficient(int n=1e5, int p=998244353) : MOD(p), fact(n + 1), fact_inv(n + 1), inv(n + 1) {
        fact[0] = fact[1] = 1;
        fact_inv[0] = fact_inv[1] = 1;
        inv[1] = 1;

        for(int i = 2; i <= n; i++) {
            fact[i] = fact[i-1] * i % MOD;
            inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
            fact_inv[i] = fact_inv[i-1] * inv[i] % MOD;
        }
    }

    long long operator() (int n, int r) {
        if(n < 0 || n < r || r < 0) return 0;
        assert(n < fact.size());
        return fact[n] * fact_inv[n-r] % MOD * fact_inv[r] % MOD;
    }
};
#line 7 "verify/yosupo/yosupo_binomial_coefficient_prime_mod.test.cpp"

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T, m;
    cin >> T >> m;

    vector<int> N(T), K(T);
    int mx = 0;
    for(int i = 0; i < T; i++) {
        cin >> N[i] >> K[i];
        mx = max(mx, N[i]);
    }

    BinomialCoefficient binom(mx, m);
    for(int i = 0; i < T; i++) {
        cout << binom(N[i], K[i]) << "\n";
    }

    return 0;
}

Back to top page