mmrz's library

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

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

2項係数mod
(math/combination.hpp)

• View this file on GitHub
• Last update: 2025-07-05 17:21:00+09:00
• Include: #include "math/combination.hpp"

2項係数mod

使い方

binomial<T> bin : 2項係数mod $M$ (型は T) のコンストラクタを呼ぶ。2項係数で扱う値の上限を $K = 1010101$ としており、型 T における $1!, 2!, …, K!$ 及びそれらの逆元の計算に比例した計算量がかかる。

bin.nCr(n, r) : $_nC_r \pmod{M}$ を返す。

概要

Verify

AtCoder

Depends on

• modint (math/modint.hpp)

Code

#pragma once

#include "modint.hpp"

#include<vector>

constexpr int max_combination = 1010101;
template<typename T>
struct binomial {

	std::vector<T> fact, inv_fact;

	binomial(){
		fact.resize(max_combination);
		inv_fact.resize(max_combination);
		fact[0] = 1, inv_fact[0] = 1;
		for(int i = 1;i < max_combination;i++){
			fact[i] = fact[i - 1];
			fact[i] *= i;
			inv_fact[i] = inv_fact[i - 1];
			inv_fact[i] /= i;
		}
	}

	T nCr(int n, int r){
		if(r < 0 || r > n)return 0;

		modint ret = fact[n];
		ret *= inv_fact[r];
		ret *= inv_fact[n - r];

		return ret;
	}
};

#line 2 "math/combination.hpp"

#line 2 "math/modint.hpp"

#include<cstdint>
#include<iostream>

template <std::uint_fast64_t Modulus> class modint {
	using u64 = std::uint_fast64_t;
public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
	constexpr u64 &value() noexcept { return a; }
	constexpr const u64 &value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept {
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept {
		return modint(*this) /= rhs;
	}
	constexpr modint &operator+=(const modint rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint &operator-=(const modint rhs) noexcept {
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint &operator*=(const modint rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint &operator/=(modint rhs) noexcept {
		u64 exp = Modulus - 2;
		while (exp) {
			if (exp % 2) {
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}

	constexpr modint& operator++() noexcept {
		if (++a == Modulus) a = 0;
		return *this;
	}
	constexpr modint operator++(int) noexcept {
		modint tmp(*this);
		++(*this);
		return tmp;
	}
	constexpr modint& operator--() noexcept {
		if (a == 0) a = Modulus;
		--a;
		return *this;
	}
	constexpr modint operator--(int) noexcept {
		modint tmp(*this);
		--(*this);
		return tmp;
	}

	friend std::ostream& operator<<(std::ostream& os, const modint& rhs) {
		os << rhs.a;
		return os;
	}
};
#line 4 "math/combination.hpp"

#include<vector>

constexpr int max_combination = 1010101;
template<typename T>
struct binomial {

	std::vector<T> fact, inv_fact;

	binomial(){
		fact.resize(max_combination);
		inv_fact.resize(max_combination);
		fact[0] = 1, inv_fact[0] = 1;
		for(int i = 1;i < max_combination;i++){
			fact[i] = fact[i - 1];
			fact[i] *= i;
			inv_fact[i] = inv_fact[i - 1];
			inv_fact[i] /= i;
		}
	}

	T nCr(int n, int r){
		if(r < 0 || r > n)return 0;

		modint ret = fact[n];
		ret *= inv_fact[r];
		ret *= inv_fact[n - r];

		return ret;
	}
};

Back to top page