划分数

划分数就是把一个数 $n$ 拆分成若干个正整数的和的方案数，其中这若干个正整数是无序的，也就是 $\{1,1,2\}$ 和 $\{1,2,1\}$ 是等价的拆分。

下面我们来讨论怎么求它。

简单 DP

我们可以设 $f_{i,j}$ 表示把 $i$ 拆分成 $j$ 个正整数的方案数。

转移有两种，要么添加一个 $1$，要么把所有数都加 $1$。

即 $f_{i,j}=f_{i-1,j-1}+f_{i-j,j}$。

那么我们要求的划分数就是 $\sum _{x=0}^n{f}_{n,x}$。复杂度 $O(n^2)$。

这个算法的优点是我们可以知道所有把 $x\le n$ 拆分成 $y\le n$ 个正整数的方案数，缺点是复杂度过高。

根号分治 DP

可以发现，大于 $\sqrt{n}$ 的数我们最多选 $\sqrt{n}$ 个，所以我们可以依靠这个来优化算法。

设 $f_{i,j}$ 表示用小于等于 $i$ 的数构成 $j$ 的方案数。

转移有两种，要么是多加一个 $i$，要么就把 $i$ 加 $1$。

即 $f_{i,j}=f_{i-1,j}+f_{i,j-i}$。

这里的 $i$ 我们只枚举到 $\sqrt{n}$，这样我们就可以知道用小于等于 $\sqrt{n}$ 拼成某个数的方案数。

设 $g_{i,j}$ 表示用 $i$ 个数大于 $\sqrt{n}$ 的数构成 $j$ 的方案数。

转移有两种，要么添加一个 $\sqrt{n}+1$，要么把所有数都加 $1$。

即 $g_{i,j}=g_{i-1,j-\sqrt{n}-1}+g_{i,j-i}$。

因为大于 $\sqrt{n}$ 的数我们最多用 $\sqrt{n}$ 个，所以 $i$ 的上限也是 $\sqrt{n}$。

那么最后的答案就是 $\sum _{x=0}^n{f}_{\sqrt{n},x}\times \left(\sum _{y=0}^{\sqrt{n}}{g}_{y,n-x}\right)$ 。即枚举小于等于 $\sqrt{n}$ 的数的和。复杂度 $O(n\sqrt{n})$。

这个算法的优点是比多项式做法容易，且复杂度优于简单 DP。缺点是我们只能求得 $n$ 的划分数。

多项式

我们可以类似背包的来构造生成函数。

设 $P$ 为划分数的生成函数，即 $P_k$ 的系数为 $k$ 的划分数。

那么就有 $P=\prod _j^{\mathrm{\infty }}\left(\sum _i{a}_i{x}^{ij}\right)$。

即枚举选择的数的大小 $j$，然后乘上它的生成函数。

根据常识，原式等于 $\prod _{j=1}^{\mathrm{\infty }}\frac{1}{1-x^j}$。

然后通过 $\ln$ 和 $\exp$ 化乘为加，就可以求得 $P$。

我们先不看 $\exp$，先算 $\ln$。那么原式就是 $-\sum _{j=1}^{\mathrm{\infty }}\ln (1-x^j)$。

考虑怎么计算 $\ln (1-x^j)$，换个元设 $u=x^j$，我们就需要求 $\ln (1-u)$。

先求导，即 $-\frac{1}{1-u}=-\sum _{i=0}^{\mathrm{\infty }}{u}^i$，然后积分，即 $-\sum _{i=1}^{\mathrm{\infty }}\frac{u^i}{i}$ 。把元换回来，即 $-\sum _{i=1}^{\mathrm{\infty }}\frac{x^{ij}}{i}$。

那么原式就成了 $\sum _{j=1}^{\mathrm{\infty }}\sum _{i=1}^{\mathrm{\infty }}\frac{x^{ij}}{i}$。

最后把这一坨 $\exp$ 一下就得到了 $P$。

不难发现当上界为 $n$ 的时候，这个求和的复杂度是 $O(n\log n)$ 的。

而求 $\exp$ 的复杂度也是 $O(n\log n)$ 的，故总复杂度为 $O(n\log n)$。

这个算法的优点是能非常快的计算出 $x\le n$ 的划分数，缺点是很复杂，且对模数有要求。

---

至此就讨论完了三种求划分数的方法。但是如果你认为这就完了那就 too young too simple, sometimes naive 了，出题人怎么可能就只考裸的划分数呢。

下面我们再讨论一下如果限制了划分出来的正整数个数，或者限制了划分出来的正整数的大小该怎么做。

我们可以发现，上述算法的【简单 DP】是很好处理前者的，【多项式】是很好处理后者的，而【根号分治 DP】中的 $f$ 可以维护后者， $g$ 可以维护前者，合并都不好维护。但是回顾上述算法，你会发现它们在最根本的思想上是相似的，而它们在这方面的性质又不一样，这就促使了我们去探究上面两个限制的关系。

引理：把划分出来的正整数排序，并形成一个阶梯图，这个图在行列上具有对偶性。

这么说比较抽象，我也不知道表达对不对，但是看了下面的图就知道了。（只看加粗部分）

这张图不管是以列划分（左），还是以行划分（右），都可以看做是一个划分数的划分，且它们一一对应。

假设柱状物的个数为数的个数，柱状物的高度是数的大小。

那么如果限制是划分出来的正整数个数不超过数 $x$ ，在左图相当于是柱状物的个数不超过 $x$，那么在右图就是柱状物的高度不超过 $x$。

也就是说，限制划分出来的正整数个数不超过 $x$，和限制划分出来的正整数的大小不大于 $x$ 在本质上是相同的。我们可以对它们进行等价的转化。

这样就可以解释为何上述三个同根的算法性质不同了。