Halc's Library

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

---

Project maintained by halc-git Hosted on GitHub Pages — Theme by mattgraham

Math/ModCombination.hpp

• View this file on GitHub
• Last update: 2024-10-22 20:55:11+09:00
• Include: #include "Math/ModCombination.hpp"

Verified with

• Verify/verify-yosupo-enumerative-combinatorics/binomial_coefficient_prime_mod.test.cpp
• Verify/verify-yuki/117.test.cpp

Code

#pragma once
#include <cstdint>
#include <vector>
template <typename T>
struct ModCombination {
    std::vector<T> fact = {1}, rev{1};
    ModCombination(uint32_t sz = 0) {
        fact.reserve(sz+1);
        rev.reserve(sz+1);
    }
    void resize(uint32_t sz) {
        sz++;
        if (fact.size() >= sz) return;
        uint32_t before = fact.size();
        fact.resize(sz);
        rev.resize(sz);
        for (uint32_t i = before; i < sz; i++) {
            fact[i] = fact[i - 1] * i;
            rev[i] = rev[i - 1] / i;
        }
    }
    T comb(int32_t n, int32_t k) {
        if (n < 0 || k < 0 || n < k) return 0;
        resize(n);
        return fact[n] * rev[n - k] * rev[k];
    }
    T perm(int32_t n, int32_t k) {
        if (n < 0 || k < 0 || n < k) return 0;
        resize(n);
        return fact[n] * rev[n - k];
    }
    T multi_comb(int32_t n, int32_t k) {
        if (k == 0) return 1;
        return comb(n + k - 1, k);
    }
};

#line 2 "Math/ModCombination.hpp"
#include <cstdint>
#include <vector>
template <typename T>
struct ModCombination {
    std::vector<T> fact = {1}, rev{1};
    ModCombination(uint32_t sz = 0) {
        fact.reserve(sz+1);
        rev.reserve(sz+1);
    }
    void resize(uint32_t sz) {
        sz++;
        if (fact.size() >= sz) return;
        uint32_t before = fact.size();
        fact.resize(sz);
        rev.resize(sz);
        for (uint32_t i = before; i < sz; i++) {
            fact[i] = fact[i - 1] * i;
            rev[i] = rev[i - 1] / i;
        }
    }
    T comb(int32_t n, int32_t k) {
        if (n < 0 || k < 0 || n < k) return 0;
        resize(n);
        return fact[n] * rev[n - k] * rev[k];
    }
    T perm(int32_t n, int32_t k) {
        if (n < 0 || k < 0 || n < k) return 0;
        resize(n);
        return fact[n] * rev[n - k];
    }
    T multi_comb(int32_t n, int32_t k) {
        if (k == 0) return 1;
        return comb(n + k - 1, k);
    }
};

Back to top page