分拆数的第三种计算方法
Elegia
2020-03-08 11:41:06
我们考虑从 Ferrers diagram 的原点引出一条 $y=x$ 的直线，它离开这个图的位置就框处了一个 $h \times h$ 的正方形，这个正方形被称为一个整数拆分的 Durfee square。那么如果我们确认了正方形的边长是 $h$，它两侧放置的就都是 $\le h$ 的整数划分。因此我们得到了整数划分的这样一个表达式：
$$
\prod_{k\ge1} \frac1{1-x^k} = \sum_{h\ge0} x^{h^2} \left(\prod_{k=1}^h \frac1{1-x^k}\right)^2
$$
在计算前 $n$ 项时，由于 $h^2\le n$，我们只需要完成前 $\sqrt n$ 项的 $h$ 即可。
因此我们只需要这几行核心代码即可完成计算，复杂度为 $\Theta(n\sqrt n)$：
```cpp
int b = sqrt(n);
ans[0] = tmp[0] = 1;
for (int i = 1; i <= b; ++i) {
for (int rep = 0; rep < 2; ++rep)
for (int j = i; j <= n - i * i; ++j)
add(tmp[j], tmp[j - i]);
for (int j = i * i; j <= n; ++j)
add(ans[j], tmp[j - i * i]);
}
```