UOJ Logo Sdchr的博客

博客

分拆数

2017-12-30 19:20:05 By Sdchr

在 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)} $$

Sdchr Avatar