stirling1

関数 · 第1種スターリング数（符号付き）s(n, 0), s(n, 1), …, s(n, n) を求める（行）

template <internal::static_modint_c mint>
std::vector<mint> stirling1(int n);

概要

第1種スターリング数（符号付き）s(n, 0), s(n, 1), …, s(n, n) を求める（行）

下降階乗 $x(x-1)\cdots(x-n+1)=\sum_k s(n,k)x^k$ を 分割統治とNTTによる多項式積で構築する。

テンプレートパラメータ

パラメータ

戻り値

長さ $n+1$ の列。k番目の要素は符号付き第1種スターリング数 $s(n,k)$

計算量

• $O(n\log^2 n)$

関連項目

• stirling1_fixed_k — 第1種スターリング数（符号付き）s(0,k), s(1,k), …, s(n,k) を求める（列固定）
• stirling2 — 第2種スターリング数 S(n, 0), S(n, 1), …, S(n, n) を求める（行）
• stirling2_fixed_k — 第2種スターリング数 S(0,k), S(1,k), …, S(n,k) を求める（列固定）