划分数（Partition Function）

问题描述

给定非负整数 $N$，计算整数划分函数 $p(n)$ 对 $n = 0, 1, \dots, N$ 的值模 $998244353$，其中 $p(n)$ 表示将 $n$ 表示为若干正整数之和（不计顺序）的方式数。

例如：
$p(0) = 1$（空划分），
$p(1) = 1$，
$p(2) = 2$（$2$, $1+1$），
$p(3) = 3$（$3$, $2+1$, $1+1+1$）。

约束条件

• $0 \leq N \leq 500\,000$

输入格式

$N$

输出格式

$p_0\ p_1\ \cdots\ p_N$ （全部模 $998244353$）

提示：可使用五边形数定理的递推式：

$$p(0) = 1,\quad p(n) = \sum_{k \ge 1} (-1)^{k+1} \left[ p\!\left(n - \frac{k(3k-1)}{2}\right) + p\!\left(n - \frac{k(3k+1)}{2}\right) \right]$$

其中当参数 $< 0$ 时对应项为 0。该递推为 $O(N\sqrt{N})$，对 $N \le 5\times10^5$ 可接受；或用生成函数 $\prod_{i=1}^\infty \frac{1}{1-x^i}$ 通过多项式求逆在 $O(N \log N)$ 内计算。

10

1 1 2 3 5 7 11 15 22 30 42