分拆数 - 入门

找到以前在校内给学弟授课用的课件，把文字版搬到这里来咧。欢迎大家提出建议或者批评！
分拆数（整数分拆）这个知识点大概用的次数不多，但是自己还是很风趣的：

• 可以利用 DP / 生成函数求解。
  
• 有时间和分析题目复杂度上界有关系。
  
• 和杨表有密切关系。
  

作为新青年，当然还是值得学习一下有木有！
分拆数

分拆数 \(p_n\) 是指将一个自然数 \(n\)，分拆成若干正整数之和的方案数。
好比说 \(3\) 可以被拆为 \(1 + 1 + 1\) 或 \(1 + 2\) 或 \(3\) 的情势，一共三种，于是 \(p_3 = 3\)。
没有额外规定的情况下，拆出来的正整数是可重集，且不在乎内部顺序（可以钦定是排序后的）。
单独规定了 \(p_0 = 1\)。
K 部分拆数

我们让 \(p(n,k)\) 表示将一个自然数 \(n\) 拆成恰好 \(k\) 个正整数之和的方案数。
于是沿着前面的例子，有 \(p(3,3) = 1\)，\(p(3,2) = 1\)，\(p(3,1) = 1\)。
单独规定了 \(p(0,0) = 1\)，其余 \(p(0,i)\) 和 \(p(i,0)\) 均为 \(0\)。
盘算分拆数

爆搜

我们总是可以从大到小放数字，定义 \(f(i,s)\) 表示目前可以放小于即是 \(i\) 的数字，还可以放的数字总和为 \(s\) 的方案数。
那么 \(f(i,s) = \sum_{x = 1}^i f(x, s - x)\) 满足 \(s - x \ge 0\)。递归求解 \(f(n,n)\) 即可。
复杂度大致是 \(O(n * p_n)\) 的，这里有个渐进估计 \(p_n \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}\)，是亚指数级的。
在一些题目里，如果出现了 \(n=50\) 这种范围，可以考虑复杂度上界是否大概与分拆数有关。
简易 DP

根据定义，我们容易发现一种分拆数 \(p_n\) 的盘算方式是把它的 \(k = 0 \dots n\) 部分拆数加起来

\[\begin{align}p_n = \sum_{k=0}^n p(n,k)\end{align}\]
求和的上界是 \(n\)，因为分拆出来的是正整数，每个数至少是 \(1\)。现在题目就酿成了，如何盘算 \(p(n,k)\) 呢？
考虑以如下办法生成一个分拆方案，初始数列为 \(\{0\}\)，进行若干轮操作，每轮：

• 先在数列末尾放入 \(x\) 个 \(0\)，可以不放。
  
• 随后数列中所有数字都加一。
  

这样做，我们就可以生成任何一个不升的数列，同时得到唯一对应的操作序列 \(X\)。考虑分拆数列和操作序列之间的关系：

• 向末尾添加 \(x\) 个 \(0\)，随后全局加一。
  
• 将所有 \(n\) 的 \(k\) 分拆，转移成了 \(n+k+x\) 的 \(k+x\) 分拆。
  

于是根据这种刻画，我们可以得到如下的求和公式，即枚举补了 \(x = 0 \dots k\) 个 \(0\) 后全局加一。

\[\begin{align}p(n,k) &= \sum_{x=0}^k p(n-k,k-x) \\       &= \sum_{x=0}^k p(n-k,x)\end{align}\]
两式是等价情势，区别是将 \(x\) 定义为了 \(k-x\)，交换了求和枚举的顺序。后者更简洁，我们背面会用第二个写法。
此时盘算每个状态需要 \(O(k)\) 次加法，而总状态数为 \(O(nk)\)，故复杂度目前是 \(O(nk^2)\)，已经比暴力好了很多。
当然还可以进一步优化，这里利用一个非常常见而且风趣的 trick，观察下面两个式子：

\[\begin{align}p(n,k) &= \sum_{x=0}^k p(n-k,x) \\p(n-1,k-1) &= \sum_{x=0}^{k-1} p(n-k,x)\end{align}\]
好像两者之间只差了一项 ?!!!

\[\begin{align}p(n,k) = p(n-1,k-1)+ p(n-k,k)\end{align}\]
于是现在盘算每个状态只需要 \(O(1)\) 次加法，得到了 \(O(nk)\) 的算法。
到现在我们已经能比较快地盘算所有 K 部分拆数了，于是在 \(O(n^2)\) 的时间里，盘算出所有 \(p_n\) 是非常简单的！
互异分拆数

诶，如果要求拆分出的每个数字不一样怎么办呢？我们稍微修改一下前面的生成方式：

• 在数列末尾放入至多一个 \(0\)（或者不放）。
  
• 数列中所有数字加一。
  

于是有 \(d(n,k) = d(n-k,k) + d(n-k, k-1)\)，前者表示没放，后者表示放了，复杂度依然是 \(O(nk)\)，但可以分析得更精致。
由于 \(1+2+3 \dots + \sqrt n = O(n^2)\)，这里的 \(k\) 不大概凌驾 \(O(\sqrt n)\)，故复杂度其实是 \(O(n \times \min(k,\sqrt n))\) 的。
Ferrers 图和 Durfee square

以 \(12\) 为例子，我们可以直观地对每种分拆给出一种共轭的分拆（翻转这个图形）。
      $12 = 5+4+2+1$
            ●●●●●
        ●●●●
        ●●
        ●
                $12 = 4+3+2+2+1$
                ●●●●
        ●●●
        ●●
        ●●
        ●
          
在原始情况下 \(p(n,k)\) 表示将 \(n\) 分为恰好 \(k\) 部的方案数。
而观察其共轭分拆，可以表示将 \(n\) 分为恣意部，最大值恰好为 \(k\) 的方案数。赋予了 \(p(n,k)\) 新的含义。
在 Ferrers 图的基础上，我们可以从左上角找到一个极大的正方形，设边长为 \(h\)，则两侧可以被视作最大值不凌驾 \(h\) 的分拆！
  ●●●●
  ●●●
  ●●
  ●●
  ●

我们不妨考虑枚举窦菲方 Durfee square 的边长 \(h\)（花费 \(h^2\) 的数值），然后算另外两个部分的方案数，以此盘算 \(p_n\)。
下文的代码来源于 EI 的文章，原文利用生成函数作为动机，但本文毕竟是入门教程，最好用非生成函数的方式解释一下：
[code]int b = sqrt(n);ans[0] = tmp[0] = 1;for (int h = 1; h