src/binomial.hpp

• View this file on GitHub
• Last update: 2025-10-08 00:44:44+09:00
• Include: #include "src/binomial.hpp"

Depends on

• src/modint.hpp
• src/template.hpp

Code

#pragma once
#include "template.hpp"
#include "modint.hpp"

template<int MAX_N> struct Binomial {
    array<mint, N + 1> fact{}, ifact{};

    constexpr Binomial(int n) {
        fa[0] = 1;
        for(int i = 1; i <= n; i++) fa[i] = fa[i - 1] * i;
        ifa[n] = fa[n].inv();
        for(int i = n; i >= 1; i--) ifa[i - 1] = ifa[i] * i;
    }

    mint C(int n, int k) const {
        if(k < 0 || k > n) return 0;
        return fa[n] * ifa[k] * ifa[n - k];
    }

    mint P(int n, int k) const {
        if(k < 0 || k > n) return 0;
        return fa[n] * ifa[n - k];
    }

    mint H(int n, int k) const {
        if(n == 0 && k == 0) return 1;
        if(n <= 0 || k < 0) return 0;
        return C(n + k - 1, k);
    }
    // n<=m+K
    mint Kata(int n, int m, int k) -> mint {
        if(n > m + k) return 0;
        return nCk(n + m, n) - nCk(n + m, n - k - 1);
    };
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/modint.hpp"

template<int mod = 998244353> struct modint {
    int x;
    constexpr modint(long x_ = 0): x(x_ % mod) {
        if(x < 0) x += mod;
    }
    constexpr modint operator-() {
        auto res = *this;
        res.x = (x ? mod - x : 0);
        return res;
    }
    constexpr modint& operator+=(modint r) {
        if((x += r.x) >= mod) x -= mod;
        return *this;
    }
    constexpr modint& operator-=(modint r) {
        if((x -= r.x) < 0) x += mod;
        return *this;
    }
    constexpr modint& operator*=(modint r) {
        x = 1LL * x * r.x % mod;
        return *this;
    }
    constexpr modint& operator/=(modint r) { return *this *= r.inv(); }
    constexpr friend modint operator+(modint a, modint b) { return a += b; }
    constexpr friend modint operator-(modint a, modint b) { return a -= b; }
    constexpr friend modint operator*(modint a, modint b) { return a *= b; }
    constexpr friend modint operator/(modint a, modint b) { return a /= b; }
    constexpr modint inv() const { return pow(mod - 2); }
    constexpr modint pow(long b) const {
        assert(0 <= b);
        modint a = *this, c = 1;
        while(b) {
            if(b & 1) c *= a;
            a *= a;
            b >>= 1;
        }
        return c;
    }
    constexpr int val() const { return x; }
    constexpr friend ostream& operator<<(ostream& os, const modint& m) { return os << m.val(); }

    constexpr friend istream& operator>>(istream& is, modint& m) {
        long v;
        is >> v;
        m = modint(v);
        return is;
    }
};
using mint = modint<>;
#line 4 "src/binomial.hpp"

template<int MAX_N> struct Binomial {
    array<mint, N + 1> fact{}, ifact{};

    constexpr Binomial(int n) {
        fa[0] = 1;
        for(int i = 1; i <= n; i++) fa[i] = fa[i - 1] * i;
        ifa[n] = fa[n].inv();
        for(int i = n; i >= 1; i--) ifa[i - 1] = ifa[i] * i;
    }

    mint C(int n, int k) const {
        if(k < 0 || k > n) return 0;
        return fa[n] * ifa[k] * ifa[n - k];
    }

    mint P(int n, int k) const {
        if(k < 0 || k > n) return 0;
        return fa[n] * ifa[n - k];
    }

    mint H(int n, int k) const {
        if(n == 0 && k == 0) return 1;
        if(n <= 0 || k < 0) return 0;
        return C(n + k - 1, k);
    }
    // n<=m+K
    mint Kata(int n, int m, int k) -> mint {
        if(n > m + k) return 0;
        return nCk(n + m, n) - nCk(n + m, n - k - 1);
    };
};

Back to top page