整数划分问题

众所周知，整数划分问题是一类计算将正整数 $n$ 无序拆分成若干可相同的正整数之和的划分数的问题，存在一类普适性的 DP 解法以及针对划分数问题的五边形数定理……

先来看一道小学奥数题。

给出 $n$ 个小球和 $m$ 个盒子，分别计算在以下情况中，将小球放入盒子（盒子不能是空）的方案数：

1. 小球和盒子都有标号
2. 小球有标号，盒子无标号
3. 小球无标号，盒子有标号
4. 小球和盒子都没有标号

显然，问题 1 可以通过简单容斥来求，即我们钦点有 $k$ 个盒子是空的，得到答案是 $\sum\limits_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n$。注意到这本质上是第二类斯特林数乘上盒子数的阶乘（见通项公式），即 $m!\begin{Bmatrix}n\newline m \end{Bmatrix}$。

对于问题 2 ，这显然是第二类斯特林数 $\begin{Bmatrix}n\newline m \end{Bmatrix}$ 的定义（组合意义？）。

对于问题 3，因为小球不可区分，所以我们考虑插板。因为盒子不空，所以答案是 $\dbinom{n-1}{m-1}$。

至此前三个问题都在 $O(nm)$ 的时间内解决掉了，但是第四个问题呢？显然我们不能直接对 3 除一个 $m!$ 了事，一个最明显的反例就是得到的结果甚至不一定是整数！

我们考虑 DP。

整数划分 DP

问题 4 可以被如下转化：

给定正整数 $n$ ，求将 $n$ 分解为 $m$ 个正整数之和的方案数。两种方案不同当且仅当 $m$ 个正整数构成的集合不相同。
$n, m\le 5000$

设 $f[i,k]$ 为考虑将 $i$ 划成 $k$ 个正整数的方案数。对于当前的状态，我们可以将其划成两种情况：

1. 当前划分包含数字 1，方案是 $f[i-1,k-1]$
2. 当前划分不含数字 1，考虑对划分出的每个数字减 1，方案数不变，得到方案数是 $f[i-k,k]$

因此转移：
$$ f[i,k]=f[i-1,k-1]+f[i - k, k] $$ 时间复杂度 $O(nm)$。

代码：

memset(f, 0, sizeof(f)), f[0][0] = 1;
for(int j = 1; j <= n; j++)
    for(int i = j; i <= n; i++)
        f[i][j] = f[i - 1][j - 1] + f[i - j][j];

一个变形

考虑这样一个问题：

给定正整数 $n$ ，求将 $n$ 分解为若干个正整数之和的方案数。两种方案不同当且仅当划分出的正整数构成的集合不相同。
$Subtask1, n \le 5000$
$Subtask2,n\le 10^5$

• Subtask1

考虑 DP，注意到这本质上就是一个完全背包计数：有 $n$ 个物品 $1,2,…,n$，选出一些让和为 $n$，物品可以取多次。然后就可以 $O(n^2)$ 快乐DP了，代码略。

• Subtask2

注意到我们有两种求划分数的 DP：第一类状态设计为 $f[i,k]$ 考虑将 $i$ 划成 $k$ 个正整数的方案数，复杂度是 $O(nk)$，即划分个数乘上划分值域；第二类是完全背包计数，复杂度是 $O(nV)$，即元素个数乘上划分值域。

考虑复杂度均摊，设阈值 $B$，我们把能用的数字划分为 $[1,B]$ 和 $[B+1,n]$ 两部分。第一部分一共有 $B$ 个能用的数字，跑完全背包计数，复杂度 $O(nB)$；第二部分不会选择超过 $\frac{n}{B}$ 个，跑第一种 DP，复杂度 $O(\frac{n^2}{B})$。最后可以模拟卷积合并 DP 结果，取 $B = \lceil\sqrt{n}\rceil$，总复杂度 $O(n\sqrt{n})$。

代码：

int x, y, n, P, f[CN], g[CN][400];
int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int work(){
    int B = ceil(sqrt(n)); 
    memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));
    f[0] = 1;
    for(int i = m; i <= B; i++) for(int j = i; j <= n; j++)
        f[j] = add(f[j], f[j - i]);
    g[0][0] = 1;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= min(B, i); j++)
        g[i][j] = add(g[i - 1][j - 1], g[i - j][j]);
    int ans = 0;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= min(B, i); j++)
        if(i + j * B <= n) // 每个数都 +B 
            g[i + j * B][0] = add(g[i + j * B][0], g[i][j]);
    for(int i = 0; i <= n; i++) // 合并状态 
        ans = add(ans, 1ll * f[i] * g[n - i][0] % P);
    return ans;
}

实际上这个问题是一类经典问题，被称作整数拆分问题，另一种解法是五边形数定理。

五边形数定理

• 五边形数
  形如 $p_n = p_{n-1}+3n-2$ 的数字被称作是五边形数，通项是 $p_n=\dfrac{n(3n-1)}{2}$。

五边形数定理指出：
$$ \phi(x) = \prod\limits_{k\ge 1}(1-x^k)=\sum\limits_{k=-\infty}^{+\infty}(-1)^kx^{p_k} $$ 其中 $p_k$ 是五边形数。
设 $f_n$ 为 $n$ 的拆分数，$F(x)$ 是 $f_n$ 的 OGF，有：
$$ F(x)=1/\phi(x) $$ 即：
$$ (1-x-x^2+x^5+x^7-…)(1+f_1x+f_2x^2+f_3x^3+…)=1 $$ 比较系数得：
$$\begin{aligned} &f_n-f_{n-1}-f_{n-2}+f_{n-5}+f_{n-7}-…=0 \newline \Leftrightarrow &f_n=f_{n-1}+f_{n-2}-f_{n-5}-f_{n-7}\end{aligned}$$ 其中数列 $1,2,5,7,12,15,…$ 对应广义五边形数 $p_1,p_{-1},p_2,p_{-2},…$。

然后我们就可以愉快的递推 $f[]$ 了，可以证明这样做的复杂度为 $O(n\sqrt{n})$。

代码：

int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int p(int x) {return x * (3 * x - 1) / 2;}
memset(f, 0, sizeof(f)), f[0] = 1;
for(int i = 1; i <= n; i++)
    for(int j = 1; ;j++){ 
        int k = p(j); if(k > i) break;
        f[i] = add(f[i], j & 1 ? f[i - k] : P - f[i - k]);
        k = p(-j); if(k > i) break;
        f[i] = add(f[i], j & 1 ? f[i - k] : P - f[i - k]);
    }