汎用 modint の階乗・逆階乗生成

components/factorial_table_generic.hpp · GitHub で見る

共通ページ

通常版・軽量版の二項係数が共有する表の生成処理です。利用者向けの階乗・逆階乗は二項係数ライブラリから取得できます。

factorial_table_detail::build<Mint, Canonical = true>(factorial,inverse_factorial,n) は、各 Mint* の先頭 n+1 要素に階乗・逆階乗を書き込みます。領域は重ならない有効な配列とし、素数法 p = Mint::mod() に対して 0 <= n < p を満たしてください。

Mint は整数からの構築・乗算・inv() に対応させます。Canonical = true かつ整数の val() を持つ型では、その剰余代表を使えるものとして扱います。false では型自身の乗算を使います。表を生成している間は法を変更しません。

逆元計算を \(O(\log p)\) として、時間は \(O(n+\log p)\)、出力配列を除く追加空間は \(O(1)\) です。

依存ライブラリ

• 32 bit Barrett 演算

検証コード

• test/binomial_prefix_sum_light.test.cpp
• test/binomial_prefix_sum_online_light.test.cpp
• test/comb.test.cpp
• test/comb_light.test.cpp
• test/comb_prime_mod.test.cpp
• test/comb_prime_mod_light.test.cpp

コード

#ifndef FACTORIAL_TABLE_GENERIC_HPP
#define FACTORIAL_TABLE_GENERIC_HPP

#include "barrett32.hpp"
#include <concepts>
#include <cstdint>
#include <limits>
#include <type_traits>

namespace factorial_table_detail {
template<class Mint, bool Canonical = true> void build(Mint *factorial, Mint *inverse_factorial, int n) {
	if constexpr (Canonical && requires(const Mint &x) { { x.val() } -> std::integral; }) {
		const auto modulus = Mint::mod();
		if (std::uint64_t(modulus) <= std::numeric_limits<std::uint32_t>::max()) {
			Barrett32 arithmetic(modulus);
			auto make = [](std::uint32_t value) { return Mint(value); };
			std::uint32_t value = 1;
			factorial[0] = make(value);
			for (int i = 1; i <= n; ++i) {
				value = arithmetic.mul(value, i);
				factorial[i] = make(value);
			}
			inverse_factorial[n] = factorial[n].inv();
			if constexpr (std::is_signed_v<decltype(inverse_factorial[n].val())>) {
				std::int64_t residue = inverse_factorial[n].val() % std::int64_t(modulus);
				value = residue < 0 ? residue + modulus : residue;
			} else value = arithmetic.reduce(inverse_factorial[n].val());
			for (int i = n; i > 0; --i) {
				value = arithmetic.mul(value, i);
				inverse_factorial[i - 1] = make(value);
			}
			return;
		}
	}
	factorial[0] = Mint(1);
	for (int i = 1; i <= n; ++i) factorial[i] = factorial[i - 1] * Mint(i);
	inverse_factorial[n] = factorial[n].inv();
	for (int i = n; i > 0; --i) inverse_factorial[i - 1] = inverse_factorial[i] * Mint(i);
}
}

#endif

Back to top page