Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Kuro-orzz/Library

:heavy_check_mark: NumberTheory/Yosupo/Binomial_coefficient_prime_mod.test.cpp

Depends on

Code

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

#include "../../template.h"

#include "../Math/Combination.h"


void solve() {
    int t; ll m; cin >> t >> m;
    Comb C(min(m - 1, (ll)1e7 - 1), m);
    while (t--) {
        int n, k; cin >> n >> k;
        cout << C.comb(n, k) << '\n';
    }
}
#line 1 "NumberTheory/Yosupo/Binomial_coefficient_prime_mod.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod"

#line 2 "template.h"

#include <bits/stdc++.h>

using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define INF32 ((1ull<<31)-1)
#define INF64 ((1ull<<63)-1)
#define inf (ll)1e18

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll r) { return uniform_int_distribution<ll>(0, r - 1)(rng); }

const int mod = 998244353;

void solve();

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);

    // int t; cin >> t;

    // while(t--)

        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 2 "Misc/ModInt.h"

template <int32_t mod>
struct ModInt {
    int32_t x;

    ModInt(): x(0) {}
    ModInt(int32_t _x): x(_x % mod) { x = x < 0 ? x + mod : x; }

    ModInt &operator += (const ModInt &p) {
        x += p.x;
        if (x >= mod) x -= mod;
        return *this;
    }

    ModInt &operator -= (const ModInt &p) {
        x -= p.x;
        if (x < 0) x += mod;
        return *this;
    }

    ModInt &operator *= (const ModInt &p) {
        x = (int32_t)(1ll * x * p.x % mod);
        return *this; 
    }

    ModInt &operator /= (const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    // ModInt += Int
    ModInt &operator += (int32_t t) { return *this += ModInt(t); }
    ModInt &operator -= (int32_t t) { return *this -= ModInt(t); }
    ModInt &operator *= (int32_t t) { return *this *= ModInt(t); }
    ModInt &operator /= (int32_t t) { return *this /= ModInt(t); }

    ModInt operator - () const { return ModInt(-x); } // -a;
    ModInt operator + () const { return ModInt(*this); } // +a;
    ModInt &operator ++ () { *this += 1; return *this; } // ++a;
    ModInt &operator -- () { *this -= 1; return *this; } // --a;
    ModInt operator ++ (int) { ModInt res = *this; *this += 1; return res; } // a++;
    ModInt operator -- (int) { ModInt res = *this; *this -= 1; return res; } // a--;

    // ModInt = ModInt + ModInt
    ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; }

    // ModInt = ModInt + Int
    ModInt operator + (int32_t t) const { return ModInt(*this) += t; }
    ModInt operator - (int32_t t) const { return ModInt(*this) -= t; }
    ModInt operator * (int32_t t) const { return ModInt(*this) *= t; }
    ModInt operator / (int32_t t) const { return ModInt(*this) /= t; }

    // ModInt = Int + ModInt
    friend ModInt operator + (int32_t t, const ModInt &p) { ModInt res(t); res += p; return res; }
    friend ModInt operator - (int32_t t, const ModInt &p) { ModInt res(t); res -= p; return res; }
    friend ModInt operator * (int32_t t, const ModInt &p) { ModInt res(t); res *= p; return res; }
    friend ModInt operator / (int32_t t, const ModInt &p) { ModInt res(t); res /= p; return res; }

    bool operator == (const ModInt &p) const { return x == p.x; }
    bool operator != (const ModInt &p) const { return x != p.x; }
    bool operator < (const ModInt &p) const { return x < p.x; }
    bool operator <= (const ModInt &p) const { return x <= p.x; }
    bool operator > (const ModInt &p) const { return x > p.x; }
    bool operator >= (const ModInt &p) const { return x >= p.x; }

    bool operator == (int32_t t) const { return x == t; }
    bool operator != (int32_t t) const { return x != t; }
    bool operator < (int32_t t) const { return x < t; }
    bool operator <= (int32_t t) const { return x <= t; }
    bool operator > (int32_t t) const { return x > t; }
    bool operator >= (int32_t t) const { return x >= t; }

    ModInt inverse() const { return power(mod - 2); }

    ModInt power(int32_t b) const {
        assert(b >= 0);
        ModInt mul(x), ret(1);
        while (b) {
            if (b & 1) ret *= mul;
            mul *= mul;
            b /= 2;
        }
        return ret;
    }

    friend istream &operator >> (istream &in, ModInt &p) { 
        int32_t t;
        in >> t;
        p = ModInt<mod>(t);
        return in;
    }
    
    friend ostream &operator << (ostream &out, const ModInt &p) { return out << p.x; }

    int32_t get() const { return x; }
    static constexpr int32_t get_mod() { return mod; }
};
#line 2 "NumberTheory/Math/Binary_exponentiation.h"

using u128 = __uint128_t;
using i128 = __int128;

ll binMul(ll a, ll b, ll M) { return (i128)a * b % M; }

// long double trick

// require: mantissa 64 bit, x86 gcc/clang

ll binMul2(ll a, ll b, ll M) {
    ll q = (ll)((long double)a * b / M);
    ll r = (ll)((unsigned ll)a * b - (unsigned ll)q * M);
    return r < 0 ? r + M : (r >= M ? r - M : r);
}

ll binMul3(ll a, ll b, ll M) {
    unsigned long long ua = a % M, um = M, res = 0;
    while (b) {
        if (b & 1) { res += ua; if (res >= um) res -= um; }
        ua <<= 1; if (ua >= um) ua -= um;
        b >>= 1;
    }
    return res;
}

ll binPow(ll a, ll b, ll M) {
    a %= M;
    ll res = 1 % M;
    while (b) {
        if (b & 1) res = (i128)res * a % M;
        a = (i128)a * a % M;
        b /= 2;
    }
    return res;
}
#line 2 "NumberTheory/Math/Extended_euclid.h"


ll extended1(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll d = extended1(b, a%b, x1, y1);
    x = y1;
    y = x1-y1*(a/b);
    return d;
}

// Iterative version

ll extended2(ll a, ll b, ll &x, ll &y) {
    x = 1, y = 0;
    ll x1 = 0, y1 = 1;
    ll a1 = a, b1 = b;
    while (b1) {
        ll q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
#line 5 "NumberTheory/Math/Combination.h"

// This modint only work for MOD is prime cuz using modulo inverse

// using mint = ModInt<MOD>;


// vector<mint> fact;


// void preprocess() {

//     fact[0] = 1;

//     for (int i = 1; i < (int)fact.size(); i++) {

//         fact[i] = fact[i-1] * i;

//     }

// }


// mint comb(int n, int k) {

//     if (k < 0 || k > n) return 0; 

//     return fact[n] / (fact[n-k] * fact[k]);

// }

// -----------------------------------------------------


// Using for n, k <= 1e6, m is prime and n < m < 2^31

struct Comb {
    ll m;
    vector<int> fact, invFact;

    Comb() {}
    Comb(int maxn, ll _m) : m(_m), fact(maxn+1), invFact(maxn+1) {
        fact[0] = 1;
        for (int i = 1; i <= maxn; i++) fact[i] = (ll)fact[i-1] * i % m;
        invFact[maxn] = binPow(fact[maxn], m-2, m);
        for (int i = maxn; i >= 1; i--) invFact[i-1] = (ll)invFact[i] * i % m;
    }

    // C(n, k) = n! / (k! * (n-k)!)

    ll comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        return 1ll * fact[n] * invFact[k] % m * invFact[n-k] % m;
    }

    // P(n,k) = n! / (n−k)!

    ll perm(int n, int k) {
        if (k < 0 || k > n) return 0;
        return 1ll * fact[n] * invFact[n-k] % m;
    }

    // inv(i) = (i-1)! / i! = 1/i

    // modulo inverse of i

    ll inv(int i) { return i <= 0 ? 0 : 1ll * invFact[i] * fact[i-1] % m; }

    // catalan(n) = C(2n, n) / (n+1)

    // require 2*n <= maxn

    ll Catalan(int n) { return 1ll * comb(2*n, n) * inv(n+1) % m; }
};


// Pascal triangle

// Using for n * k <= 1e7 or n,k <= 5000, O(1) per operation

vector<vector<int>> preprocess(int n, int k, int m) {
    vector<vector<int>> C(n+1, vector<int>(k+1));
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1 % m;
        for (int j = 1; j <= min(i, k); j++) {
            C[i][j] = (1ll * C[i-1][j-1] + C[i-1][j]) % m;
        }
    }
    return C;
}

// m must be prime

// fermat's little theorem a^(m-2) ≡ a^(-1)

ll inverse1(ll a, ll m) { return binPow(a, m-2, m); }
// m must be prime

// base on extended euclid trick

ll inverse2(ll a, ll m) { return a <= 1 ? a : m-m/a * inverse2(m % a, m) % m; }
// m coprime to a, gcd(a, m) = 1

// extended euclid trick

ll inverse3(ll a, ll m) {
    ll x, y;
    extended2(a, m, x, y);
    return (x % m + m) % m;
}
#line 5 "NumberTheory/Yosupo/Binomial_coefficient_prime_mod.test.cpp"

void solve() {
    int t; ll m; cin >> t >> m;
    Comb C(min(m - 1, (ll)1e7 - 1), m);
    while (t--) {
        int n, k; cin >> n >> k;
        cout << C.comb(n, k) << '\n';
    }
}
Back to top page