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)$ 。

评论

yww
orzypl
WrongAnswer
好强啊。我还以为这玩意儿只能 $O(n\sqrt n)$ 求呢……

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。