This documentation is automatically generated by online-judge-tools/verification-helper
#include "library/sequence/partition_number.hpp"
シグネチャ
template <typename mint>
std::vector<mint> partition_number(int n)
概要
分割数 $P_0,\ldots,P_N$ を計算します.ここで,$P_i$ は,正整数を要素とする多重集合であって,総和が $i$ であるようなものの個数と一致します.
母関数は $\displaystyle \sum_{i=0} ^ \infty P_i x ^ i=\prod_{k=1} ^ \infty \dfrac{1}{1-x ^ k}$ で表され,オイラーの五角数定理 :
\[\prod_{k=1} ^ \infty(1-x ^ k)=\sum_{k=-\infty} ^ \infty(-1) ^ k x ^ {k(3k-1)/2}\]を用いることで,
\[\begin{aligned} \sum_{i=0} ^ n P_i x ^ i &=\left(1+\sum_{k=1} ^ n (-1) ^ k \Bigl(x ^ {k(3k-1)/2}+x ^ {k(3k+1)/2}\Bigr)\right) ^ {-1}\bmod x ^ {n+1} \end{aligned}\]により計算できます.
テンプレート引数
mint
: modint 型を想定返り値
分割数 $\{P_i\} _ {i=0} ^ N$
制約
時間計算量
$O(n\log n)$
参考