cp-library
競技プログラミング用 C++ ライブラリ
軽量な階乗・逆階乗テーブル
components/factorial_table_light.hpp · GitHub で見る
共通ページ · 軽量実装
軽量な二項係数の共通部品です。通常版 FPS を読み込まず、light_factorial_detail::Table<Mint>(max_n) で階乗・逆階乗を計算します。
素数法 \(p=\texttt{Mint::mod()}\) に対し、上限は \(N=\min(\texttt{max\_n},p-1)\) です。factorial[i]、inverse_factorial[i]、構築時の modulus を持ちます。max_n は非負で INT_MAX 未満にし、構築した表を使っている間は法を変更しません。
Mint は整数からの構築、乗算、mod() と inv() に対応する型を指定します。階乗は前から、逆階乗は末尾の逆元を 1 回だけ求めて後ろから生成します。
構築は \(O(N+\log p)\) 時間、\(O(N)\) 空間です。逆元計算を \(O(\log p)\) とします。
依存ライブラリ
検証コード
コード
#ifndef FACTORIAL_TABLE_LIGHT_HPP
#define FACTORIAL_TABLE_LIGHT_HPP
#include "../math/mint.hpp"
#include "factorial_table_generic.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
namespace light_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);
factorial_table_detail::build<Mint, !std::is_same_v<Mint, mint>>(factorial.data(), inverse_factorial.data(), n);
}
};
}
#endif
#line 1 "components/factorial_table_light.hpp"
#line 1 "math/mint.hpp"
#include <cassert>
#include <istream>
#include <ostream>
#include <type_traits>
#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif
namespace mint_detail {
template <class I>
constexpr bool mint_integral = std::is_integral_v<I>
#if defined(__SIZEOF_INT128__)
|| std::is_same_v<I, __int128> || std::is_same_v<I, unsigned __int128>
#endif
;
struct [[gnu::warn_unused]] Mint {
using mint = Mint;
unsigned v = 0;
[[nodiscard]] static constexpr unsigned mod() { return 998244353; }
[[nodiscard, gnu::always_inline]] static unsigned reduce(unsigned long long x) {
return (x + (unsigned long long)(unsigned(x) * 998244351u) * mod()) >> 32;
}
[[gnu::always_inline]] Mint() = default;
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
Mint(I x) {
long long r = x % (long long)mod();
if (r < 0) r += mod();
v = reduce((unsigned long long)r * 932051910);
}
[[nodiscard, gnu::always_inline]] static Mint raw(unsigned x) {
Mint a;
a.v = reduce((unsigned long long)x * 932051910);
return a;
}
[[nodiscard, gnu::always_inline]] static Mint word(unsigned x) {
Mint a;
a.v = x;
return a;
}
[[nodiscard, gnu::always_inline]] unsigned val() const {
unsigned r = reduce(v);
return r < mod() ? r : r - mod();
}
friend std::istream &operator>>(std::istream &is, Mint &x) {
long long value;
if (is >> value) x = Mint(value);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Mint &x) {
return os << x.val();
}
[[gnu::always_inline]] Mint &operator+=(Mint b) {
v += b.v;
if (v >= 2 * mod()) v -= 2 * mod();
return *this;
}
[[gnu::always_inline]] Mint &operator-=(Mint b) {
v -= b.v;
if (v >> 31) v += 2 * mod();
return *this;
}
[[gnu::always_inline]] Mint &operator*=(Mint b) {
v = reduce((unsigned long long)v * b.v);
return *this;
}
Mint &operator/=(Mint b) { return *this *= b.inv(); }
Mint &operator++() { return *this += Mint(1); }
Mint &operator--() { return *this -= Mint(1); }
Mint operator++(int) {
Mint a = *this;
++*this;
return a;
}
Mint operator--(int) {
Mint a = *this;
--*this;
return a;
}
[[nodiscard, gnu::always_inline]] Mint operator+() const { return *this; }
[[nodiscard, gnu::always_inline]] Mint operator-() const { return word(v ? 2 * mod() - v : 0); }
[[nodiscard, gnu::always_inline]] Mint operator+(Mint b) const { return Mint(*this) += b; }
[[nodiscard, gnu::always_inline]] Mint operator-(Mint b) const { return Mint(*this) -= b; }
[[nodiscard, gnu::always_inline]] Mint operator*(Mint b) const { return Mint(*this) *= b; }
[[nodiscard]] Mint operator/(Mint b) const { return Mint(*this) /= b; }
[[nodiscard, gnu::always_inline]] bool operator==(Mint b) const { return (v < mod() ? v : v - mod()) == (b.v < mod() ? b.v : b.v - mod()); }
[[nodiscard, gnu::always_inline]] bool operator!=(Mint b) const { return !(*this == b); }
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
[[nodiscard]] friend Mint operator+(I a, Mint b) { return Mint(a) + b; }
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
[[nodiscard]] friend Mint operator-(I a, Mint b) { return Mint(a) - b; }
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
[[nodiscard]] friend Mint operator*(I a, Mint b) { return Mint(a) * b; }
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
[[nodiscard]] friend Mint operator/(I a, Mint b) { return Mint(a) / b; }
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
[[nodiscard]] friend bool operator==(I a, Mint b) { return Mint(a) == b; }
template <class I, std::enable_if_t<mint_integral<I>, int> = 0>
[[nodiscard]] friend bool operator!=(I a, Mint b) { return Mint(a) != b; }
[[nodiscard]] Mint pow(long long n) const {
assert(n >= 0);
if (!n) return Mint(1);
Mint r(1), a = *this;
for (; n > 1; n >>= 1, a *= a)
if (n & 1) r *= a;
return r * a;
}
[[nodiscard, gnu::noinline]] Mint inv() const {
assert(*this != Mint(0));
Mint a2 = *this * *this, a3 = a2 * *this;
Mint a7 = a3 * a3 * *this;
Mint a31 = a7;
for (int i = 0; i < 2; ++i) a31 *= a31;
a31 *= a3;
Mint r = a7;
for (int i = 0; i < 3; ++i) r *= r;
r *= a3;
r *= r;
for (int j = 0; j < 4; ++j) {
for (int i = 0; i < 5; ++i) r *= r;
r *= a31;
}
for (int i = 0; i < 3; ++i) r *= r;
return r * a7;
}
};
} // namespace mint_detail
using mint = mint_detail::Mint;
using fps_mint = mint;
#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif
#line 1 "components/factorial_table_generic.hpp"
#line 1 "components/barrett32.hpp"
#line 5 "components/barrett32.hpp"
#include <cstdint>
struct Barrett32 {
std::uint32_t mod;
std::uint64_t reciprocal;
explicit Barrett32(std::uint32_t m) : mod(m), reciprocal(m > 1 ? std::uint64_t((__uint128_t(1) << 64) / m) : 0) {
assert(m > 0);
}
std::uint32_t reduce(std::uint64_t x) const {
if (mod == 1) return 0;
std::uint64_t q = (__uint128_t(x) * reciprocal) >> 64, r = x - q * mod;
return r < mod ? r : r - mod;
}
std::uint32_t mul(std::uint32_t a, std::uint32_t b) const { return reduce(std::uint64_t(a) * b); }
std::uint32_t pow(std::uint32_t a, std::uint64_t e) const {
std::uint32_t r = mod == 1 ? 0 : 1;
for (; e; e >>= 1, a = mul(a, a)) if (e & 1) r = mul(r, a);
return r;
}
};
#line 5 "components/factorial_table_generic.hpp"
#include <concepts>
#line 7 "components/factorial_table_generic.hpp"
#include <limits>
#line 9 "components/factorial_table_generic.hpp"
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);
}
}
#line 6 "components/factorial_table_light.hpp"
#include <algorithm>
#line 11 "components/factorial_table_light.hpp"
#include <vector>
namespace light_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);
factorial_table_detail::build<Mint, !std::is_same_v<Mint, mint>>(factorial.data(), inverse_factorial.data(), n);
}
};
}