組み合わせ (src/math/combination.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-09-04 17:24:30+09:00
Include: #include "src/math/combination.hpp"

Verified with

test/math/combination/atcoder_abc145_d.test.cpp

Code

#ifndef MATH_COMBINATION_HPP
#define MATH_COMBINATION_HPP

#include <array>

template<class T, int SIZE = 1100000, T MOD = 1000000007>
class Combination {
private:
	std::array<T, SIZE> fac, finv, inv;

public:
	Combination() {
		fac[0] = fac[1] = inv[1] = finv[0] = finv[1] = 1;
		for (int i = 2; i < SIZE; ++i) {
			fac[i] = fac[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

	T inverse(int n) { return inv[n]; }

	T factorial(int n) { return fac[n]; }

	T inverse_factorial(int n) { return finv[n]; }

	T permutation(int n, int r) {
		if (n < r || n < 0 || r < 0) return 0;
		return fac(n) * finv(n - r);
	}

	T combination(int n, int r) {
		if (n < r || n < 0 || r < 0) return 0;
		return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
	}
};

#endif // MATH_COMBINATION_HPP

#line 1 "src/math/combination.hpp"



#include <array>

template<class T, int SIZE = 1100000, T MOD = 1000000007>
class Combination {
private:
	std::array<T, SIZE> fac, finv, inv;

public:
	Combination() {
		fac[0] = fac[1] = inv[1] = finv[0] = finv[1] = 1;
		for (int i = 2; i < SIZE; ++i) {
			fac[i] = fac[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

	T inverse(int n) { return inv[n]; }

	T factorial(int n) { return fac[n]; }

	T inverse_factorial(int n) { return finv[n]; }

	T permutation(int n, int r) {
		if (n < r || n < 0 || r < 0) return 0;
		return fac(n) * finv(n - r);
	}

	T combination(int n, int r) {
		if (n < r || n < 0 || r < 0) return 0;
		return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
	}
};