在 uoj 上瞎写一篇博客，随便玩玩。。。

$f(n)$ 表示 $n$ 的分拆方案数，例如 $4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 3 = 2 + 2 = 4$ ，所以 $f(4) = 5$ 。

设 $F(x)$ 为 $f$ 的生成函数，即 $F(x) = \sum_{i = 0} ^ {\infty} f_i x ^ i$ ，则有

$$ \begin{aligned} F(x) & = (x ^ 0 + x ^ 1 + x ^ 2 + ...) (x ^ 0 + x ^ 2 + x ^ 4 + ...) ... \\ & = \prod_{i = 1} ^ {\infty} \sum_{j = 0} ^ {\infty} x ^ j \\ & = \prod_{i = 1} ^ {\infty} \frac{1}{1 - x ^ i} \end{aligned} $$

对等式两边同时取 ln ，有

$$ \ln F(x) = - \sum_{i = 1} ^ {\infty} \ln (1 - x ^ i) $$

考虑将 $\ln (1 - x)$ 进行展开，设 $h(x) = \ln (1 - x)$ ，对两边求导，有

$$ h'(x) = - \frac{1}{1 - x} = - \sum_{i = 0} ^ {\infty} x ^ i $$

再对两边同时积分，有

$$ \ln (1 - x) = h(x) = -\sum_{i = 1} ^ {\infty} \frac{x ^ i}{i} $$

将上述等式代入 $F(x)$ ，得

$$ \begin{aligned} \ln F(x) & = \sum_{i = 1} ^ {\infty} \sum_{j = 1} ^ {\infty} \frac{x ^ {ij}}{j} \\ & = \sum_{t = 1} ^ {\infty} x ^ t \sum_{j | t} \frac{1}{j} \end{aligned} $$

对两边同时取 exp ，得

$$ F(x) = e ^ {\sum_{t = 1} ^ {\infty} x ^ t \sum_{j | t} \frac{1}{j}} $$

在调和级数的复杂度下预处理出 $g(t) = \sum_{j | t} \frac{1}{j}$ ，然后就可以在 $O(n \log n)$ 的时间内处理出 $f(1), f(2), ..., f(n)$ 。

update : 2018-2-3

上面的东西仅仅思想可以借鉴，如果单纯为了解决分拆数，有很多更简便的做法。。

分拆数可以分块 DP 做，$f[i][j]$ 表示当前选择了 $i$ 个大于 $\sqrt n$ 的数，和为 $j$ 的方案数，$g[i][j]$ 表示当前考虑了大于 $\sqrt n$ 以及不超过 $i$ 的数，和为 $j$ 的方案数。

更巧妙的做法是利用五边形数定理，对比系数可以在 $O(n \sqrt n)$ 求出，利用多项式求逆可以 $O(n \log n)$ 。

$$ \Phi(x) = \prod_{i = 1} ^ {\infty} (1 - x ^ i) = \prod_{i \in Z} (-1) ^ i x ^ {i(3i \pm 1) / 2} $$

然后

$$ F(x) = \frac{1}{\Phi(x)} $$