分拆数

考虑分拆数的生成函数 \(\prod\limits_{i = 1}^n \frac{1}{1 - x^i}\)。

研究分母，相当于是互异分拆数，奇数个数被统计 \(-1\) 次，偶数个数被统计 \(1\) 次。

考虑 Ferrers 图，发现在大部分情况下互异奇数分拆数和互异偶数分拆数可以互相转换。设斜边长度为 \(s\)，底边长度为 \(b\)。发现当 \(b = s + 1\) 或 \(b = s\) 且底边和斜边有公共点时才无法转换，否则可以把斜边平移到最下面，或把底平移到斜边上。

此时要么 \(n = \frac{s(3s - 1)}{2}\) 或 \(n = \frac{s(3s + 1)}{2}\)。

所以 \((p_0 x^0 + p_1 x^1 + p_2 x^2 + \cdots) (1 + \sum\limits_{k \ge 1} (-1)^k x^{\frac{k(3k - 1)}{2}}) = 1\)，对比系数得 \(p_n = \sum\limits_{k \ge 1} (-1)^{k + 1} p_{n - \frac{k(3k \pm 1)}{2}}\)。

直接递推即可做到 \(O(n \sqrt n)\) 计算。