型を指定する階乗・逆階乗テーブル（高速版）

components/factorial_table.hpp · GitHub で見る

全体サイト（256 KiB向け） · 高速実装

軽量実装（64 KiB）はこちら

modint 型ごとに階乗・逆階乗を構築する内部部品です。通常は二項係数ライブラリを利用します。

factorial_detail::Table<Mint>(max_n) は、素数 Mint::mod() に対し 0 から min(max_n,Mint::mod()-1) まで前計算します。factorial[i] が階乗、inverse_factorial[i] が逆階乗、modulus が構築時の法です。構築後の modint の法は変更しないでください。変更した場合は新しいテーブルを構築します。

Mint は整数からの構築、乗算、mod() と inv() に対応するものを使います。max_n は 0 以上 INT_MAX 未満とします。

実際の前計算上限を \(N\)、法を \(p\) とすると、構築は \(O(N+\log p)\) 時間、\(O(N)\) 空間です。modint の乗算を \(O(1)\)、逆元計算を \(O(\log p)\) とします。

依存ライブラリ

• 32 bit Barrett 演算
• 汎用 modint の階乗・逆階乗生成
• modint998244353 の共通剰余演算
• modint998244353 の階乗・逆階乗生成
• modint998244353

検証コード

• test/comb.test.cpp
• test/comb_prime_mod.test.cpp

コード

#ifndef FACTORIAL_TABLE_HPP
#define FACTORIAL_TABLE_HPP

#include "mint_factorials.hpp"
#include "factorial_table_generic.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>

namespace factorial_detail {
template<class Mint> struct Table {
	decltype(Mint::mod()) modulus;
	std::vector<Mint> factorial, inverse_factorial;
	explicit Table(int max_n) : modulus(Mint::mod()) {
		assert(0 <= max_n && max_n < std::numeric_limits<int>::max() && modulus > 1);
		int n = static_cast<int>(std::min(std::uint64_t(max_n), std::uint64_t(modulus) - 1));
		factorial.resize(n + 1), inverse_factorial.resize(n + 1);
		if constexpr (std::is_same_v<Mint, mint>) {
			mint_detail::factorials(factorial.data(), inverse_factorial.data(), n + 1);
		} else factorial_table_detail::build(factorial.data(), inverse_factorial.data(), n);
	}
};
}

#endif

Back to top page