浅谈整数分拆

· · 个人记录

例题。（无序分拆数）

将 n 拆分成若干正整数（可重复）之和，不区分顺序，求方案数。

做法 1（搜索）

直接暴力枚举分拆即可，期望通过数据为 n\le 50 左右。

做法 2（DP）

令 f(i,j) 为使用了 1\sim i，和为 j 的方案数。

朴素地，有：f(i,j)\gets f(i-1,j-ki) \quad \text{where } 0\le k\le j/i

运用经典的滚动数组优化，可以做到 \Theta(n^2)。

做法 3（Another DP）

令 g(i,j) 为使用了 i 个数，和为 j 的方案数。

转移考虑：给这 i 个数都加上 1；或者新开一个数。具体地可以考虑一个整数分拆的图。

也就是：g(i,j)\gets g(i,j-i)+g(i-1,j-1)。

时间复杂度 \Theta(n^2)。

正确性证明：如下图。

这张图中，格子的数量表示被表示的数，例如这里表示的就是 10；每一行的列数表示分拆，例如这里表示的就是 10=5+4+1，注意每一行的列数要求递减。

这张图被称为杨图（Young diagram）或 Ferrers 图。

做法 2 可以视为按行 DP，而做法 3 可以视为按列 DP。由于每一行的列数是递减的，所以唯一性显然。

习题：解释 g(i,j) 转移在杨图中的几何意义。

做法 4（根号分治）

例题。（NOI Online #1 跑步）求正整数 n（n\le 10^5）的无序分拆数。模数给定。

前两种做法时间复杂度均为 \Theta(n^2)，无法通过。

注意到一个事实：在 n 的表示中，\gt \sqrt n 的数出现次数不会超过 \sqrt n。这启示我们结合做法 2 和做法 3。

具体地，令 m=\lfloor\sqrt n\rfloor。做法 2 转移至 m，而对于做法 3，我们将状态修改为「必须使用 \gt m 的数」。这样只需要维护行长度 \gt m 的杨图，转移就是将 j-1 改成 j-m-1。

这样两个 DP 都在 \Theta(n^{1.5}) 的时间复杂度内完成。合并是平凡的。

做法 5（GF）

令 F(z) 为分拆数的生成函数，不难得到

F(z)=\prod_{1\le i}\sum_{j\ge 0} z^{ij}=\prod_{1\le i}\frac{1}{1-z^i}

运用经典的 \ln-\exp 的技巧可以做到 \Theta(n\log n)，这里不再赘述。

做法 6（五边形数定理）

略。

整数分拆往往可以用在一些困难的题目中。

例题。（「AHOI 2022」山河重整）

求有多少个 S\subseteq [n] 满足存在 T\subseteq S，使得 n=\sum_{i\in T}i。1\le n\le 5\times 10^5，对给定模数（不一定是素数）取模。

寻找充要条件。 令 A=\{1,2,\ldots,\sum_{i\in S}i\}。则一个充要条件是：\forall i\in A，S 中{}\le i 的数的和不小于 i。

必要性是显然的。充分性留作习题。

知道了这一点后，容易设计一个 \Theta(n^2) 的 DP。但是没有前途，这里不再赘述。

正难则反，考虑容斥。考虑一个不合法的方案应该怎么不重不漏地被计数。

由充要条件，可以知道，必然存在一个 1\le i\le n，使得{}\le i 的数的和 \lt i。不妨设 i 是第一个不满足的位置，由假设得，\le i-1 的数的和 \ge i-1，所以 \le i 的数的和 =i-1。换言之，1\sim i-1 这个前缀满足 \le i-1 的数的和 =i-1，且能表示出 [i-1] 中的每一个数。

这启示我们设计状态 f(i) 表示 [i] 中和为 i，且能表示出 [i] 中的每一个数的子集数。答案显然为 \displaystyle 2^n-\sum_{0\le i\lt n} f(i)2^{n-1-i}。考虑如何求出 f。

令 g(i) 为 [i] 中满足和为 i 的子集数，我们考虑容斥：用 g(i) 减掉「不能表示出 [i] 中的每一个数」的方案数。由于集合内数互不相同，我们可以直接做到 \Theta(n^{1.5}) 求出 g(i)。

为了方便理解，我们具体地讲解 DP 实现。

还是这张图。我们仍然要按列 DP。显然列长度最长是 \Theta(\sqrt n) 的。

由于每个数都不相同，所以显然每一列的长度相差至多为 1，单调递减。这意味着，若图中长度最大的列为 k，则 k-1,k-2,\ldots 的列都会存在。

具体来看代码实现。我们从大到小枚举每一列的长度 i，由于每一列长度相差至多为 1，所以首先要强制选择第 i 列；接下来再做一个完全背包即可。

我们以 n=9 为例。转移完 i=3 之后是这个样子的：

然后我们强制选择 i=2 的一列：

然后做完全背包之后就是这个样子的：

然后强制加入 i=1 的一列：

不难发现这样确实不重不漏地计数了。

这里给出另一种理解：由于拆分出的数的数量不大于 \sqrt n，将 「计数 \Theta(\sqrt n) 个不同数字和为 n 的方案数」变为「对 i\in [1,n]，考虑有多少个数 \ge i」。（by CXY07）。

注意观察这张图：以拆分 9=4+3+2 为例，这意味着，图中列数 \ge 4 的行数为 1，列数 \ge 3 的行数为 2，列数 \ge 2 的行数为 3。

观察图中的每一列。从左往右看，行数为 3 的列数为 \textcolor{cyan}{2}（这意味着，有 3 行长度大于 \textcolor{cyan}{2}），长度为 2 的列数为 \textcolor{cyan}{1}（这意味着，有 2 行长度大于 3=\textcolor{cyan}{2+1}），长度为 1 的列数为 \textcolor{cyan}{1}（这意味着，有 1 行长度大于 4=\textcolor{cyan}{2+1+1}）。

我们得到结论：杨表中，行数{}\ge x 的列数 y，意义为选择了 x 个 \ge y 的数。

所以代码长成这样：

for (int i=n; i; --i) if (i*(i+1)/2<=n) {
    for (int j=n; j>=i; --j) g[j]=g[j-i]; // 强制选择
    g[i]++; // 加入自成一列的方案数
    for (int j=i; j<=n; ++j) g[j]+=g[j-i];
}

其中，g[j]++ 是 i 自成一列的方案数。

容易发现时间复杂度为 \Theta(n^{1.5})。

当然我们还有 GF 解释（参考 一叶知秋 的题解）：我们本质上就是要求出 \displaystyle G(z)=\prod_{1\le i\le n}(1+z^i)。

考虑一个杨图，高为 n，将其第 i 行删去 i 列，边缘左对齐。这构成了一张新的杨图，只是高{}\le n。由此可得

\prod_{1\le i\le n}(1+z^i)=\sum_{1\le h}z^{h(h+1)/2}\prod_{1\le i\le h}\frac{1}{1-z^i}

我们就是在从大到小枚举 h。对于每个 h，我们

不难发现这是对的。

紧接着我们可以知道：\displaystyle f(i)=g(i)-\sum_{j\lt i} f(j)\operatorname{val}(j+2,i)。这里 \operatorname{val}(j+2,i) 表示用 [j+2,i] 间的数凑出 (i-j) 的方案数。令 h(i)=\sum_{j\lt i} f(j)\operatorname{val}(j+2,i)。

有一个很神仙的观察：h(i) 实际上可以认为是一种「带权的整数拆分」，由 f(j) 加上 \{j+2,\cdots,i\} 转移过来。它和之前 g 的转移本质相同。

还是考虑杨图。从大到小枚举 i 转移。

枚举到 i 的时候，首先先强制在右边添加上一列 i。

然后对于每个 j，如果 i 自成一列的话，它的宽度至少要 j+2。然后再做一个多重背包即可。

这个东西的生成函数就是 \displaystyle \prod_{i\ge j+2}(1+z^i)=\sum_{1\le h}z^{h(h+1)/2}z^{\textcolor{cyan}{(j+1)}h}\prod_{1\le i\le h}\frac{1}{1-z^i}，可以用类似的手法证明。于是就得到

f(i)=g(i)-[z^i]\sum_{j}f(j)z^j\sum_{1\le h}z^{h(h+1)/2}z^{\textcolor{cyan}{(j+1)}h}\prod_{1\le i\le h}\frac{1}{1-z^i}

然后枚举 h，再枚举外层的 j，照猫画虎转移就可以了。

实现里面为什么是 f(j)\to z^{(j+2)h+j}：因为之前乘以了 z^{h}。下面的代码也是可以通过的。

for (int i=n; i; --i) if (i*(i+1)/2<=n) {
    for (int j=0; j<=n; ++j) 
        if (j+i*(j+1)<=n) g[j+i*(j+1)]+=f[j];
    for (int j=n; j>=i; --j) g[j]=g[j-i];
    for (int j=i; j<=n; ++j) g[j]+=g[j-i];
}

由于转移 h 时要求之前的 DP 值已经求出，考虑使用 CDQ 分治优化 DP。但是注意到 \mathrm{val}(j+2,i)\neq 0，当且仅当 i\ge 2j+2，所以右半区间内的贡献总是 0，所以可以用类似倍增的方式转移。

使用倍增转移，时间复杂度 \Theta(n^{1.5}+n^{1.5}/2+\cdots)=\Theta(n^{1.5})。

例题。（青春有悔）

有 n 个随机变量，X_i 等概率随机，且独立地取 [0,a_i] 中的整数。

所有数字均不大于 $10^5$。