partition_function

関数 · 分割数を $p(0)$ から $p(n)$ まで列挙する

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

概要

分割数を $p(0)$ から $p(n)$ まで列挙する

生成関数 $\prod_{k\ge1}(1-x^k)^{-1}$ の分母を五角数定理で構築し、 形式的冪級数の逆元を求める。

テンプレートパラメータ

パラメータ

戻り値

長さ $n+1$ の列。i番目の要素は分割数 $p(i)$

計算量

• $O(n\log n)$