分拆数 - 生成函数

上一篇 分拆数 - 入门 我们介绍了一些 DP 方法。实际上分拆数在表示为生成函数（形式幂级数）以后会非常牛！（还是背包！）

生成函数

可能有些同学不熟悉，所以我们从头介绍。考虑等比数列求和公式 \(1 + x^k + x^{2k} + x^{3k} \dots = \cfrac{1}{1 - x^k}\)。

这个式子左边的意思是：只使用数字 \(k\)，我们有多少种拼出 \(c\) 的方案呢？答案是 \(x^c\) 的系数。

我们可以把 \(k = 1,2 \dots\) 对应的多项式乘起来，得到 \(\cfrac{1}{1 - x^1} \cfrac{1}{1 - x^2} \cfrac{1}{1 - x^3} \dots = 1 + p_1 x^1 + p_2 x^2 + p_3 x^3 \dots\)

因为做乘法时，指数位置相加，系数相乘（做了个背包），因此这个多项式每项的系数恰好就是分拆数啦，即：

\[P(x) = \sum_{k=0}^{\infty} p(k)x^k = \prod_{i=1}^{\infty} \frac{1}{1 - x^i} \]

我们的目标是求出多项式 \(P(x) \pmod{x^{n+1}}\) 的各项系数。

手法

观察发现右侧是连乘，心动伐，我们对两边取自然对数 \(\ln\)，将连乘改写为连加：

\[\ln P(x) = \sum_{i=1}^{\infty} -\ln(1 - x^i) \]

接下来我们可以利用泰勒展开/麦克劳林展开 \(-\ln(1 - x) = \sum_{j=1}^{\infty} \cfrac{x^j}{j}\)，代入右侧得到：

\[\ln P(x) = \sum_{i=1}^{\infty} \sum_{j=1}^{\infty} \frac{x^{ij}}{j} \]

此时指数上出现了 \(ij\)，故可以暴力枚举 \(i,j\) 计算每项 \(x^k\) 的系数，这里的复杂度是由调和级数 \(O(n \log n)\) 保证的，如果有读者不熟悉：

\[O\left(\sum_{i=1}^n \frac{n}{i}\right) = O(n \log n) \]

诶那么此时我们已经得到了 \(\ln P(x) \pmod{x^{n+1}}\) 每一项的系数，只需要做多项式 \(\exp\) 回去即可，得到了复杂度为 \(O(n \log n)\) 的好结果。

欧拉函数（五边形数定理）

我们希望求出 \(P(x)\) 的系数：

\[\prod_{i=1}^{\infty} \frac{1}{1 - x^i} \]

不妨考察其分母，其恰好为欧拉函数的展开式：

\[\prod_{i=1}^{\infty} (1 - x^i) = \phi(x) \]

欧拉五边形数定理指出，这个这个无穷连乘展开后，大多数项会正负相抵，保留下来的非零项较少，且其指数恰好是广义五边形数：

\[\prod_{i=1}^{\infty} (1 - x^i) = \sum_{k=-\infty}^{\infty} (-1)^k x^{\frac{k(3k-1)}{2}} \]

其中我们可以钦定枚举 \(k\) 的顺序为 \(0,1,-1,2,-2 \dots\)，展开结果如下：

\[\phi(x) = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \dots \]

手法

因为互为倒数，我们不妨考察 \(P(x) \phi(x) = 1\)，展开这个式子：

\[\left( \sum_{n=0}^{\infty} p(n)x^n \right) \left( 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots \right) = 1 \]

这个式子的值为 \(1\)，意思是说，展开后左侧任何 \(x^c\) 的系数都必须为 \(0\)，故对任意 \(x^n\) 而言都有：

\[p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - p(n-12) - p(n-15) + \dots = 0 \]

而项数只有大约 \(\sqrt{\frac{2n}{3}}\) 个，于是这个算法可以在 \(O(n \sqrt n)\) 时间内求解 \(p_1,p_2 \dots p_n\)。