軽量な階乗・逆階乗と二項係数

math/comb_light.hpp · GitHub で見る

共通ページ · 軽量実装

階乗・逆階乗と二項係数の高速実装はこちら

#define COMB_MAX 500000
#include "lib/math/comb_light.hpp"

int main() {
	using light_combinatorics::comb, light_combinatorics::fact, light_combinatorics::finv;
	assert(comb(10, 3).val() == 120);
	assert(fact[5] * finv[5] == mint(1));
}

light_combinatorics 名前空間の comb・Comb<Mint>・fact・finv を使います。通常版と同じ添字形式で、負の添字は 0 を返します。COMB_MAX の既定値は 10000000 です。通常版とは独立した実装で、同時に include できます。

各 modint 型の最初の有効な問い合わせで階乗・逆階乗を生成し、その型の全操作で表を共有します。使わない型、負の添字、範囲外の k を 0 とする問い合わせでは前計算しません。main より前の呼び出しにも対応します。既定の mint も同じ方式です。

操作	内容
comb(n,k) / comb<Mint>(n,k)	二項係数。n < 0・k < 0・k > n なら 0
Comb<Mint>::comb(n,k)	型を指定した二項係数
fact[i] / finv[i]	既定の mint の階乗／逆階乗。i < 0 なら 0
Comb<Mint>::fact[i] / Comb<Mint>::finv[i]	指定型の階乗／逆階乗。i < 0 なら 0

Mint は素数法で、整数からの構築、乗算、mod()、inv() に対応する型にします。atcoder::modint1000000007 なども使え、ACL 自体は依存に含みません。非負の i・n は min(COMB_MAX,Mint::mod()-1) 以下にします。法を変更できる型は、変更後の最初の有効な問い合わせで表を作り直します。

上限を \(N=\min(\texttt{COMB\_MAX},p-1)\)、法を \(p\) とすると、型ごとの初回前計算は \(O(N+\log p)\) 時間・\(O(N)\) 空間、その後の問い合わせは \(O(1)\) 時間・追加空間です。逆元計算を \(O(\log p)\) とします。

依存ライブラリ

• 32 bit Barrett 演算
• 汎用 modint の階乗・逆階乗生成
• 軽量な階乗・逆階乗テーブル
• modint998244353

検証コード

• test/comb_light.test.cpp
• test/comb_prime_mod_light.test.cpp

コード

#ifndef COMB_LIGHT_HPP
#define COMB_LIGHT_HPP

#include "../components/factorial_table_light.hpp"

#ifndef COMB_MAX
#define COMB_MAX 10000000
#endif

namespace light_combinatorics {
inline constexpr int COMB_INF = static_cast<int>(COMB_MAX);
static_assert(COMB_INF >= 0 && COMB_INF < mint::mod());
namespace detail {
template<class Mint>
const light_factorial_detail::Table<Mint>& table() {
	static light_factorial_detail::Table<Mint> value(COMB_INF);
	if (value.modulus != Mint::mod()) value = light_factorial_detail::Table<Mint>(COMB_INF);
	return value;
}
template<class Mint, bool Inverse> struct Factorial {
	Mint operator[](int i) const {
		if (i < 0) return Mint(0);
		assert(i <= COMB_INF);
		const auto& value = table<Mint>();
		assert(std::size_t(i) < value.factorial.size());
		if constexpr (Inverse) return value.inverse_factorial[i];
		else return value.factorial[i];
	}
};
}

template<class Mint = mint>
Mint comb(int n, int k) {
	if (n < 0 || k < 0 || k > n) return Mint(0);
	assert(n <= COMB_INF);
	const auto& value = detail::table<Mint>();
	assert(std::size_t(n) < value.factorial.size());
	return value.factorial[n] * value.inverse_factorial[k] * value.inverse_factorial[n - k];
}

template<class Mint = mint> struct Comb {
	inline static constexpr detail::Factorial<Mint, false> fact{};
	inline static constexpr detail::Factorial<Mint, true> finv{};
	static Mint comb(int n, int k) { return light_combinatorics::comb<Mint>(n, k); }
};
inline constexpr auto& fact = Comb<>::fact;
inline constexpr auto& finv = Comb<>::finv;
}

#endif

Back to top page