2025年整数划分问题

整数划分

先给出几个定义：

一、整数的划分
将正整数 $n$ 拆分成若干个正整数的和就叫做整数的划分。

二、整数的 $k$ 划分
即将其拆分成若干个不大于 $k$ 的正整数的和。

三、整数的 $k$ 分部划分
即将其拆分成 $k$ 个正整数的和。

四、有序划分和无序划分
有序划分即顺序有关的划分，例如 $1 + 2$ 与 $2 + 1$ 被视为 $3$ 的不同的划分。而无序划分则是顺序无关的。

五、划分数
即对应条件下的划分的方案数。
在本文中，将 $n$ 的无序划分数记为 $B_n$ ，将 $n$ 的无序 $k$ 划分数记为 $B_k(n)$ ，将 $n$ 的无序 $k$ 分部划分数记为 $B_{n,k}$ 。

本文的重点在于如何求各种不同的划分数。

有序划分

整数 $n$ 的 $k$ 分部划分数为 $C_{n-1}^{k-1}$ 。

这不难理解： $f_{n,k}=\sum \limits _{i=1}^n f_{n-i,k-1}$ ，平凡的有其值等于 $C_{n-1}^{k-1}$ 。

$n$ 的有序划分数为 $\sum\limits_{i=1}^nC_{n-1}^{k-1}=2^{n-1}$ 。

而 $n$ 的有序 $k$ 划分数满足 $f_{n,k}=\sum\limits_{i=1}^kf_{n-i,k}$ ，是一个经典的线性递推式。不过由于其特征多项式为 $\frac{x^{k+1}-2x^k+1} {x-1}$ ，可以做到 $O (n)$ 取模，因此可以做到 $O (n)$ 或 $\log k \log n)$ 求值。

有序划分较易理解，这里不再赘述。本文重点在于下面的无序划分。

无序划分

动态规划法

先从朴素的角度切入。

考虑 $n$ 的 $k$ 划分。

我们可以使用 $k$ ，也可以不使用 $k$ 。

因此有 $B_k(n)=B_k(n-k)+B_{k-1}(n)$ 。

注意当 $\ge k$ 有 $B_{k}(n)=B_{k}(k)$ 。

现在考虑无序 $k$ 分部划分。

我们知道对于其任意一个合法的划分有 $\sum\limits_{i=1}^{k}a_i=n$ 且 $a_i\ge 1$ 。

由于 $a_i \ge 1$ 的条件不好处理，因此我们令 $b_i=a_i-1$ 。

则有 $\sum\limits_{i=1}^{k}b_i=n-k,b_i \ge 0$ 。

我们可以考虑将值为 $0$ 的去掉。

因此 $\sum\limits_{i=1}^{j}b_i=n-k,b_i\ge1,1\le j\le k$ 。

由于顺序无关，我们可以将任意一种 $a$ 的方案以此法一一映射到 $b$ 的一种方案。

因此有 $B_{n,k}=\sum\limits_{i=1}^{k} B_{n-k,i}$ 。

这样直接转移是 $O(nk^2)$ 的。

将转移方程稍微变形：

$B_{n,k}=\sum_{i=1}^{k} B_{n-k,i}=\sum_{i=1}^{k-1}B_{n-k,i}+B_{n-k,k}=B_{n-1,k-1}+B_{n-k,k}$

这样就是 $O (n k)$ 了。

我们发现这个递推式与 $k$ 划分是向一致的，只是这两个数列初始边界差异才导致了两个数列的差异。我们尝试考虑两个数列的联系：

无序性实际上加一个限制 $a_i \le a_{i+1}$ 即可。

将一中拆分方案抽象为图形，那么这实际上就是一张各列高度递增的网格图，由于平面的特性我们可以将其旋转 $\degree$ 得到一个新的方案。

实质上我们在做的就是：记 $b_i=\sum\limits_{j=1}^{k}[a_j\ge i]$ ，则 $\sum\limits_{j=1}^{\max\{a\}}b_i=n$ 且 $b_1=k,b_i\ge b_{i+1}$ 。

因此我们可以得到 $n$ 的无序 $k$ 分部划分数等于 $n$ 的最大分部值为 $k$ 的方案数，于是就有 $B_{n,k}=B_{k}(n)-B_{k-1}(n)$ 。

若 $b_2 =k$ 则 $a_i \ge 2$ ，我们可以令 $a_i$ 都减去 $1$ 。否则我们可以在 $b$ 中去掉 $b_1=k$ ，这样就得到了 $B_{n,k}=B_{n-k,k}+B_{n,k-1}$ 。

当然根据 $B_{n,k}=B_{k}(n)-B_{k-1}(n)$ 也能得到以上递推式，这也很好解释了为何两个数列的初始边界有所不同。

上述算法的复杂度较大，我们尝试继续优化。

生成函数法

我们尝试从生成函数的角度切入。

先考虑 $n$ 的 $k$ 划分。

我们可以选任意多的 $1$ 到 $k$ 之间的数，且需要使之总和为 $n$ 。两种方案不同等价于任意一个数选的个数不同。

因此我们可以构造 $\sum\limits_{j=0}^{\infty}x^{ij}$ 表示选取 $j$ 个 $i$ 的方案。

那么

$\sum\limits_{n=0}^{\infty} B_{k}(n)x^n=\prod_{i=1}^{k}(\sum\limits_{j=0}^{\infty}x^{ij})=\frac{1} {\prod_{i=1}^{k}(1-x^i)}$

显然我们可以转为线性递推来解决这个问题，其特征多项式为 $\prod_{i=1}^{k}(x^i-1)$ 。并且我们可以根据 $x^n \bmod (x^i-1)=x^{n \bmod i}$ 列出同余方程组。

复杂度 $O(k^2\log^2 k)$ ，注意这是一个与 $n$ 无关的复杂度。

但这样 $k$ 较大而 $n$ 的阶比 $k$ 并不是高很多的时候效率较低。考虑是否有其他的处理方式。

暴力乘法是 $O (n k)$ 的，无法继续优化，尝试变换思路。

事实上我们只需要求 $\bmod x^{n+1}$ 。超过 $n + 1$ 的项是无需计算的。

由于乘法无法继续优化，且我们只需要取函数的前几项，因此我们对函数取对数转为加法。

$\ln f(x)=\ln \frac{1} {\prod_{i=1}^{k}(1-x^i)} =-\sum_{i=1}^{k}\sum_{j=1}^{\infty} \frac{-x^{ij}} {j}=\sum_{i=1}^{k}\sum_{j=1}^{\infty} \frac{x^{ij}} {j}$

我们只需要计算前 $n + 1$ 项，因此求 $\ln f(x)$ 的复杂度为 $O(n\log k)$ 。

最后多项式 $\exp$ 即可。总复杂度 $\log n)$ 。

而根据 $B_{n,k}=B_{k}(n)-B_{k-1}(n)$ ，我们有 $n$ 的 $k$ 分部划分的生成函数为

$\sum\limits_{n=0}^{\infty} B_{n,k}x^n=\sum\limits_{n=0}^{\infty} B_{k}(n)x^n-\sum\limits_{n=0}^{\infty} B_{k-1}(n)x^n=(\frac{1}{1-x^k}-1)\frac{1} {\prod_{i=1}^{k-1}(1-x^i)}=\frac{x^k} {\prod_{i=1}^{k}(1-x^i)}$

求法与 $k$ 划分是一样的。

根据 $B_n=B_{\infty}(n)$ 有 $n$ 划分数的生成函数为

$\sum_{n=0}^{\infty}B_nx^n=\frac{1} {\prod_{i=1}^{\infty}(1-x^i)}=\frac{1}{1+\sum\limits_{i=1}^{\infty}(-1)^ix^{\frac{i(3i\pm1)} {2}}}$

这里用到了五边形数。

可以使用 $\sqrt n)$ 的递推或 $O(n\log n)$ 的多项式求逆。但要注意这个问题不能转化为线性递推问题。