Combination (二項係数)
(lib/enumerative_combinatorics/combination_modint.hpp)

• View this file on GitHub
• Last update: 2025-01-18 04:43:36+09:00
• Include: #include "lib/enumerative_combinatorics/combination_modint.hpp"

Required by

• Stirling Number of the Second Kind (第 2 種スターリング数) (lib/enumerative_combinatorics/stirling_number_2nd.hpp)
• lib/math/pow_sum.hpp
• Taylor Shift (lib/polynomial/taylor_shift.hpp)

Verified with

• test/library_checker/enumerative_combinatorics/stirling_number_of_the_second_kind.test.cpp
• test/library_checker/enumerative_combinatorics/stirling_number_of_the_second_kind_fixed_k.test.cpp
• test/library_checker/polynomial/polynomial_taylor_shift.test.cpp

Code

#pragma once

/**
 * @brief Combination (二項係数)
 */

#include <vector>

template <typename T>
struct Combination{
    std::vector<T> memo, memoinv, inv;
    Combination() : memo(2, T(1)), memoinv(2, T(1)), inv(2, T(1)){}

    void init(const int N){
        if((int) memo.size() >= N + 1){
            return;
        }
        int prev_len = memo.size();
        memo.resize(N + 1);
        memoinv.resize(N + 1);
        inv.resize(N + 1);

        T m = -1;
        long long mod = (m.val + 1LL);
        for(int i = prev_len; i <= N; ++i){
            memo[i] = memo[i - 1] * i;
            inv[i] = mod - inv[mod % i] * (mod / i);
            memoinv[i] = memoinv[i - 1] * inv[i];
        }
    }

    inline T fact(const int n) {
        init(n);
        return memo[n];
    }
    inline T factinv(const int n) {
        init(n);
        return memoinv[n];
    }
    inline T ncr(const int n, const int r) {
        if(n < r || r < 0) return 0;
        init(n);
        return (memo[n] * memoinv[r]) * memoinv[n - r];
    }
    inline T npr(const int n, const int r) {
        if(n < r || r < 0) return 0;
        init(n);
        return memo[n] * memoinv[n - r];
    }
    // 重複組み合わせ
    inline T nhr(const int n, const int r) {
        if(n == 0 && r == 0) return 1;
        return ncr(n + r - 1, r);
    }
    // ボールの数、一個以上必要な箱の数、制限がない箱の数 (箱区別あり)
    // a = 0 の場合は重複組み合わせ
    inline T choose(const int n, const int a, const int b = 0) {
        if(n == 0) return !a;
        return ncr(n + b - 1, a + b - 1);
    }
    // +1 n 個, -1 m 個, 累積和 >= 0
    inline T cataran(const int n, const int m) {
        return ncr(n + m, n) - ncr(n + m, n - 1);
    }
    // +1 n 個, -1 m 個, 累積和 > -k
    inline T cataran(const int n, const int m, const int k) {
        if(m < k) return ncr(n + m, n);
        if(m < n + k) return ncr(n + m, n) - ncr(n + m, m - k);
        return 0;
    }
    // +1 n 個, -1 m 個, 累積和 < +k
    inline T cataran2(const int n, const int m, const int k) {
        return cataran(m, n, k);
    }
};

#line 2 "lib/enumerative_combinatorics/combination_modint.hpp"

/**
 * @brief Combination (二項係数)
 */

#include <vector>

template <typename T>
struct Combination{
    std::vector<T> memo, memoinv, inv;
    Combination() : memo(2, T(1)), memoinv(2, T(1)), inv(2, T(1)){}

    void init(const int N){
        if((int) memo.size() >= N + 1){
            return;
        }
        int prev_len = memo.size();
        memo.resize(N + 1);
        memoinv.resize(N + 1);
        inv.resize(N + 1);

        T m = -1;
        long long mod = (m.val + 1LL);
        for(int i = prev_len; i <= N; ++i){
            memo[i] = memo[i - 1] * i;
            inv[i] = mod - inv[mod % i] * (mod / i);
            memoinv[i] = memoinv[i - 1] * inv[i];
        }
    }

    inline T fact(const int n) {
        init(n);
        return memo[n];
    }
    inline T factinv(const int n) {
        init(n);
        return memoinv[n];
    }
    inline T ncr(const int n, const int r) {
        if(n < r || r < 0) return 0;
        init(n);
        return (memo[n] * memoinv[r]) * memoinv[n - r];
    }
    inline T npr(const int n, const int r) {
        if(n < r || r < 0) return 0;
        init(n);
        return memo[n] * memoinv[n - r];
    }
    // 重複組み合わせ
    inline T nhr(const int n, const int r) {
        if(n == 0 && r == 0) return 1;
        return ncr(n + r - 1, r);
    }
    // ボールの数、一個以上必要な箱の数、制限がない箱の数 (箱区別あり)
    // a = 0 の場合は重複組み合わせ
    inline T choose(const int n, const int a, const int b = 0) {
        if(n == 0) return !a;
        return ncr(n + b - 1, a + b - 1);
    }
    // +1 n 個, -1 m 個, 累積和 >= 0
    inline T cataran(const int n, const int m) {
        return ncr(n + m, n) - ncr(n + m, n - 1);
    }
    // +1 n 個, -1 m 個, 累積和 > -k
    inline T cataran(const int n, const int m, const int k) {
        if(m < k) return ncr(n + m, n);
        if(m < n + k) return ncr(n + m, n) - ncr(n + m, m - k);
        return 0;
    }
    // +1 n 個, -1 m 個, 累積和 < +k
    inline T cataran2(const int n, const int m, const int k) {
        return cataran(m, n, k);
    }
};

Back to top page