cp-library
競技プログラミング用 C++ ライブラリ
階乗・逆階乗生成
components/fps_factorials.hpp · GitHub で見る
共通ページ
旧 fps_detail 名を利用するコード向けの互換ヘッダーです。FPS 本体を含むライブラリ内部では mint_detail の共通部品を直接使います。実装は modint998244353 の階乗・逆階乗生成 と共有し、NTT には依存しません。通常は 階乗・逆階乗と二項係数 や Taylor Shift を利用します。factorials には mint* または法 998244353 の内部 Montgomery ワードへのポインタを渡せます。
| 関数 | 内容・返り値 | 計算量 |
|---|---|---|
fps_detail::factorials(fact,invfact,n) |
fact[i] = i!、invfact[i] = 1/i! を先頭 n 要素へ書き込む |
\(O(n)\) |
fps_detail::factorials8(fact,invfact,n) |
AVX2 版。n >= 256
|
\(O(n)\) |
fps_detail::factorial_chain<reverse>(out,chunk,value,factor) |
AVX2 の 8 レーンで積の列を生成。各レーンの value を書き、factor を掛けて進める |
\(O(\mathrm{chunk})\) |
fps_detail::factorial_transpose(x) |
AVX2 の 8×8 個の 32 bit 要素を転置する | \(O(1)\) |
factorials の引数は内部ワード版では \(0\le n<998244353\)、mint* 版では \(0\le n\le998244353\) とし、出力先はそれぞれ n 要素を持つ重ならない領域にします。n = 0 では書き込みません。256 要素以上の AVX2 対応 x86 では 32 本の積の列を並行して生成し、それ以外ではスカラー処理を使います。Mac ARM でも factorials を利用できます。
末尾に 8 が付く関数と factorial_chain・factorial_transpose は x86 のみで定義され、AVX2 に対応する CPU から呼び出します。factorial_chain は chunk を正の 8 の倍数とし、out に 8 * chunk 要素を用意します。第 s レーンの列は第 s 区間に置かれ、reverse = true のときは逆順で書き、乗数を 1 ずつ減らします。偽のときは順に書き、乗数を 1 ずつ増やします。
factorials・factorials8 は時間 \(O(n)\)、factorial_chain は時間 \(O(\mathrm{chunk})\)、factorial_transpose は時間 \(O(1)\) です。出力領域を除く追加空間はいずれも \(O(1)\) です。
依存ライブラリ
コード
#ifndef CP_COMPONENTS_FPS_FACTORIALS_HPP
#define CP_COMPONENTS_FPS_FACTORIALS_HPP
#include "mint_factorials.hpp"
namespace fps_detail {
using mint_detail::factorials;
#if defined(__x86_64__) || defined(__i386__)
using mint_detail::factorials8, mint_detail::factorial_chain, mint_detail::factorial_transpose;
#endif
}
#endif
#line 1 "components/fps_factorials.hpp"
#line 1 "components/mint_factorials.hpp"
#line 1 "components/mint_arithmetic.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 5 "components/mint_arithmetic.hpp"
#if defined(__x86_64__) || defined(__i386__)
#include <immintrin.h>
#endif
#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif
namespace mint_detail {
struct Ops {
using T = mint;
typedef unsigned int U __attribute__((may_alias));
static constexpr U mod = 998244353, twice = 2 * mod, one = 301989884;
static U reduce(unsigned long long x) { return T::reduce(x); }
static U mul(U a, U b) { return reduce((unsigned long long)a * b); }
static U add(U a, U b) {
U c = a + b;
return c < twice ? c : c - twice;
}
static U sub(U a, U b) {
U c = a - b;
return c < twice ? c : c + twice;
}
static U in(U a) { return mul(a, 932051910); }
static U out(U a) {
a = reduce(a);
return a < mod ? a : a - mod;
}
static U quotient(U r) { return ((unsigned long long)r << 32) / mod; }
static U fixed_mul(U a, U r, U q) {
return a * r - U(((unsigned long long)a * q) >> 32) * mod;
}
#if defined(__x86_64__) || defined(__i386__)
static bool vectorized() {
#if defined(__AVX2__)
return true;
#else
static const bool available = __builtin_cpu_supports("avx2");
return available;
#endif
}
using I8 = __m256i;
__attribute__((target("avx2"))) static I8 load8(const U *a) {
return _mm256_loadu_si256(reinterpret_cast<const I8 *>(a));
}
__attribute__((target("avx2"))) static void store8(U *a, I8 x) {
_mm256_storeu_si256(reinterpret_cast<I8 *>(a), x);
}
__attribute__((target("avx2"), always_inline)) static inline I8 reduce8(I8 x, I8 y) {
I8 r = _mm256_set1_epi32(998244351), p = _mm256_set1_epi32(mod);
x = _mm256_add_epi64(x, _mm256_mul_epu32(_mm256_mul_epu32(x, r), p));
y = _mm256_add_epi64(y, _mm256_mul_epu32(_mm256_mul_epu32(y, r), p));
return _mm256_blend_epi32(_mm256_srli_epi64(x, 32), y, 0xaa);
}
__attribute__((target("avx2"))) static I8 mul8(I8 a, I8 b) {
return reduce8(_mm256_mul_epu32(a, b), _mm256_mul_epu32(_mm256_srli_epi64(a, 32), _mm256_srli_epi64(b, 32)));
}
__attribute__((target("avx2"))) static I8 fixed_mul8(I8 a, I8 r, I8 q) {
I8 x = _mm256_srli_epi64(_mm256_mul_epu32(a, q), 32);
I8 y = _mm256_mul_epu32(_mm256_srli_epi64(a, 32), q);
I8 t = _mm256_blend_epi32(x, y, 0xaa);
return _mm256_sub_epi32(_mm256_mullo_epi32(a, r),
_mm256_mullo_epi32(t, _mm256_set1_epi32(mod)));
}
__attribute__((target("avx2"))) static I8 fixed_even8(I8 a, I8 r, I8 q) {
I8 t = _mm256_srli_epi64(_mm256_mul_epu32(a, q), 32);
return _mm256_sub_epi64(_mm256_mul_epu32(a, r),
_mm256_mul_epu32(t, _mm256_set1_epi32(mod)));
}
__attribute__((target("avx2"))) static I8 add8(I8 a, I8 b) {
I8 x = _mm256_add_epi32(a, b);
return _mm256_min_epu32(x, _mm256_sub_epi32(x, _mm256_set1_epi32(twice)));
}
__attribute__((target("avx2"))) static I8 sub8(I8 a, I8 b) {
I8 x = _mm256_sub_epi32(a, b);
return _mm256_min_epu32(x, _mm256_add_epi32(x, _mm256_set1_epi32(twice)));
}
#endif
};
}
#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif
#line 5 "components/mint_factorials.hpp"
namespace mint_detail {
#if defined(__x86_64__) || defined(__i386__)
__attribute__((target("avx2"))) inline void factorial_transpose(Ops::I8 (&x)[8]) {
Ops::I8 a[8], b[8];
for (int i = 0; i < 8; i += 2) {
a[i] = _mm256_unpacklo_epi32(x[i], x[i + 1]);
a[i + 1] = _mm256_unpackhi_epi32(x[i], x[i + 1]);
}
for (int i = 0; i < 8; i += 4) {
b[i] = _mm256_unpacklo_epi64(a[i], a[i + 2]);
b[i + 1] = _mm256_unpackhi_epi64(a[i], a[i + 2]);
b[i + 2] = _mm256_unpacklo_epi64(a[i + 1], a[i + 3]);
b[i + 3] = _mm256_unpackhi_epi64(a[i + 1], a[i + 3]);
}
for (int i = 0; i < 4; ++i) {
x[i] = _mm256_permute2x128_si256(b[i], b[i + 4], 0x20);
x[i + 4] = _mm256_permute2x128_si256(b[i], b[i + 4], 0x31);
}
}
template<bool reverse>
__attribute__((target("avx2"))) inline void factorial_chain(Ops::U* out, int chunk, Ops::I8 value, Ops::I8 factor) {
using I = Ops::I8;
I step = _mm256_set1_epi32(Ops::one);
I order = _mm256_setr_epi32(7, 6, 5, 4, 3, 2, 1, 0);
for (int j = 0; j < chunk; j += 8) {
I block[8];
for (int k = 0; k < 8; ++k) {
block[k] = value;
value = Ops::mul8(value, factor);
if constexpr (reverse) factor = Ops::sub8(factor, step);
else factor = Ops::add8(factor, step);
}
factorial_transpose(block);
for (int k = 0; k < 8; ++k) {
if constexpr (reverse) Ops::store8(out + (k + 1) * chunk - j - 8, _mm256_permutevar8x32_epi32(block[k], order));
else Ops::store8(out + k * chunk + j, block[k]);
}
}
}
__attribute__((target("avx2"))) inline void factorials8(Ops::U* fact, Ops::U* invfact, int n) {
using I = Ops::I8;
using U = Ops::U;
const int chunk = n / 256 * 8, covered = chunk * 32;
alignas(32) U factor[32], products[32], starts[33], inverse[33];
I p[4], x[4], step = _mm256_set1_epi32(Ops::one);
for (int i = 0; i < 32; ++i) factor[i] = Ops::in(i * chunk + 1);
for (int k = 0; k < 4; ++k) p[k] = _mm256_set1_epi32(Ops::one), x[k] = Ops::load8(factor + 8 * k);
for (int i = 0; i < chunk; ++i) {
for (int k = 0; k < 4; ++k) p[k] = Ops::mul8(p[k], x[k]), x[k] = Ops::add8(x[k], step);
}
for (int k = 0; k < 4; ++k) Ops::store8(products + 8 * k, p[k]);
starts[0] = Ops::one;
for (int i = 0; i < 32; ++i) starts[i + 1] = Ops::mul(starts[i], products[i]);
U last = starts[32];
for (int i = covered; i < n; ++i) fact[i] = last, last = Ops::mul(last, Ops::in(i + 1));
last = mint::word(last).inv().v;
for (int i = n - 1; i >= covered; --i) last = Ops::mul(last, Ops::in(i + 1)), invfact[i] = last;
inverse[32] = last;
for (int i = 31; i >= 0; --i) inverse[i] = Ops::mul(inverse[i + 1], products[i]);
for (int k = 0; k < 4; ++k) {
factorial_chain<false>(fact + 8 * k * chunk, chunk, Ops::load8(starts + 8 * k), Ops::load8(factor + 8 * k));
alignas(32) U values[8], factors[8];
for (int j = 0; j < 8; ++j) {
const int end = (8 * k + j + 1) * chunk;
values[j] = Ops::mul(inverse[8 * k + j + 1], Ops::in(end));
factors[j] = Ops::in(end - 1);
}
factorial_chain<true>(invfact + 8 * k * chunk, chunk, Ops::load8(values), Ops::load8(factors));
}
}
#endif
inline void factorials(Ops::U* fact, Ops::U* invfact, int n) {
if (!n) return;
#if defined(__x86_64__) || defined(__i386__)
if (n >= 256 && Ops::vectorized()) {
factorials8(fact, invfact, n);
return;
}
#endif
Ops::U value = Ops::one;
for (int i = 0; i < n; ++i) fact[i] = value, value = Ops::mul(value, Ops::in(i + 1));
value = mint::word(fact[n - 1]).inv().v;
for (int i = n - 1; i >= 0; --i) invfact[i] = value, value = Ops::mul(value, Ops::in(i));
}
template<class T> requires std::is_same_v<T, mint>
inline void factorials(T* fact, T* invfact, int n) {
assert(0 <= n && unsigned(n) <= mint::mod());
static_assert(sizeof(mint) == sizeof(Ops::U) && std::is_trivially_copyable_v<mint>);
if (unsigned(n) == mint::mod()) {
factorials(fact, invfact, n - 1);
fact[n - 1] = -fact[n - 2];
invfact[n - 1] = -invfact[n - 2];
return;
}
factorials(reinterpret_cast<Ops::U*>(fact), reinterpret_cast<Ops::U*>(invfact), n);
}
}
#line 5 "components/fps_factorials.hpp"
namespace fps_detail {
using mint_detail::factorials;
#if defined(__x86_64__) || defined(__i386__)
using mint_detail::factorials8, mint_detail::factorial_chain, mint_detail::factorial_transpose;
#endif
}