正整数拆分的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题给定 $1 \le N \le 4000$ ~1 \le N \le 4000~，要求统计把 $N$ ~N~ 拆成至少两个正整数之和的方案数：拆分不计顺序，加数可以重复，输出方案数对 $2147483648$ ~2147483648~ 取模的结果。

枚举所有拆分再计数是行不通的： $N = 4000$ ~N = 4000~ 时真实的拆分数已经超过 $10^{60}$ ~10^{60}~，是个天文数字。正确的做法是把「不计顺序的拆分」等价地看成「每种加数各取多少份」，于是问题变成「用面额 $1 \sim N$ ~1 \sim N~ 的物品装满容量为 $N$ ~N~ 的背包有多少种装法」，这正是完全背包的模型，可以在 $O(N^2)$ ~O(N^2)~ 的时间内算出答案。

分析

核心观察

第一个观察是「不计顺序」带来的简化：一种拆分被「每个正整数各出现了多少次」唯一确定，而不是被一个序列确定。例如 $4 = 1 + 3$ ~4 = 1 + 3~ 与 $4 = 3 + 1$ ~4 = 3 + 1~ 是同一种拆分； $4 = 1 + 1 + 2$ ~4 = 1 + 1 + 2~、 $4 = 1 + 2 + 1$ ~4 = 1 + 2 + 1~ 与 $4 = 2 + 1 + 1$ ~4 = 2 + 1 + 1~ 也是同一种。换句话说， $N$ ~N~ 的每种拆分都对应一个由正整数组成的多重集合，我们只需要数出有多少个这样的多重集合。

第二个观察是额外的那条限制很好处理： $N$ ~N~ 单独成拆（只有 $1$ ~1~ 个加数 $N$ ~N~）本身也是「把 $N$ ~N~ 写成若干正整数之和」的一种方案，只是不满足「至少拆分成 $2$ ~2~ 个数」。除此之外的拆分全部合法，所以答案就是「 $N$ ~N~ 的全部拆分数」减 $1$ ~1~。

第三个观察是「加数可以重复」恰好是完全背包的特征：把 $1, 2, \ldots, N$ ~1, 2, \ldots, N~ 都当作物品，每种物品都有无限多件，问装满容量为 $N$ ~N~ 的背包有多少种装法。背包的装法只由每种物品取了多少件决定，与取的先后顺序无关，这与「不计顺序的拆分」一一对应。

思路

设 $f_j$ ~f_j~ 表示把 $j$ ~j~ 拆成若干正整数之和（不计顺序）的方案数。先定下递推的基底：把 $0$ ~0~ 拆开只有「空拆分」这一种方案，令 $f_0 = 1$ ~f_0 = 1~。

然后从小到大依次把加数 $i = 1, 2, \ldots, N$ ~i = 1, 2, \ldots, N~ 加入可用的集合，每加入一个 $i$ ~i~ 就把整个数组更新一遍：

$\displaystyle f_j \leftarrow f_j + f_{j-i} \qquad (j = i,\, i+1,\, \ldots,\, N)$

这条转移把方案按「用不用加数 $i$ ~i~」分成两类：更新前的 $f_j$ ~f_j~ 统计的是一个 $i$ ~i~ 都不用的方案数；而「至少用一个 $i$ ~i~」的方案，可以先取出一个 $i$ ~i~，剩下的 $j-i$ ~j-i~ 再用当前允许的加数任意拆分，方案数恰好是 $f_{j-i}$ ~f_{j-i}~。两者相加就覆盖了全部情况。

内层循环的方向是关键： $j$ ~j~ 必须从小到大枚举。这样计算 $f_j$ ~f_j~ 时读到的 $f_{j-i}$ ~f_{j-i}~ 已经在本轮被更新过，同一个加数 $i$ ~i~ 就能在一种方案中重复出现任意多次，这正是完全背包的标准写法；如果 $j$ ~j~ 从大到小枚举，读到的 $f_{j-i}$ ~f_{j-i}~ 还是加入 $i$ ~i~ 之前的值，同一个 $i$ ~i~ 至多只能用一次，那统计的就是「加数互不相同」的方案数，答案会偏小。

循环范围也需要注意：外层 $i$ ~i~ 只需枚举到 $N$ ~N~，因为比 $N$ ~N~ 大的加数不可能参与 $N$ ~N~ 的拆分；内层从 $j = i$ ~j = i~ 开始，因为 $j < i$ ~j < i~ 时 $f_{j-i}$ ~f_{j-i}~ 没有意义。

最后有两个细节：

取模：每做一次加法就取一次模。模数 $2147483648 = 2^{31}$ ~2147483648 = 2^{31}~ 已经超过 32 位有符号整数能表示的最大值 $2147483647$ ~2147483647~，所以 $f$ ~f~ 数组与全部中间结果都要用 64 位整数保存。
减一：算出的 $f_N$ ~f_N~ 里包含了「只有 $N$ ~N~ 自己」这一种拆分，而题目要求至少 $2$ ~2~ 个加数，因此输出 $(f_N - 1) \bmod 2147483648$ ~(f_N - 1) \bmod 2147483648~。

具体示例

以题面样例 $N = 7$ ~N = 7~ 为例，把 $7$ ~7~ 的全部 $15$ ~15~ 种拆分按加数个数分组列出：

加数个数	拆分
$1$ ~1~	$7$ ~7~
$2$ ~2~	$6+1$ ~6+1~， $5+2$ ~5+2~， $4+3$ ~4+3~
$3$ ~3~	$5+1+1$ ~5+1+1~， $4+2+1$ ~4+2+1~， $3+3+1$ ~3+3+1~， $3+2+2$ ~3+2+2~
$4$ ~4~	$4+1+1+1$ ~4+1+1+1~， $3+2+1+1$ ~3+2+1+1~， $2+2+2+1$ ~2+2+2+1~
$5$ ~5~	$3+1+1+1+1$ ~3+1+1+1+1~， $2+2+1+1+1$ ~2+2+1+1+1~
$6$ ~6~	$2+1+1+1+1+1$ ~2+1+1+1+1+1~
$7$ ~7~	$1+1+1+1+1+1+1$ ~1+1+1+1+1+1+1~

一共 $15$ ~15~ 种，其中只有第一行（单个加数 $7$ ~7~）不合法，所以答案为 $15 - 1 = 14$ ~15 - 1 = 14~，与样例输出一致。

再用完全背包手动走一遍 $f_0 \sim f_7$ ~f_0 \sim f_7~。下表中第 $i$ ~i~ 行表示「已经允许使用加数 $1 \sim i$ ~1 \sim i~」时各 $f_j$ ~f_j~ 的值，第 $0$ ~0~ 行是初始状态：

已允许的加数	$f_0$ ~f_0~	$f_1$ ~f_1~	$f_2$ ~f_2~	$f_3$ ~f_3~	$f_4$ ~f_4~	$f_5$ ~f_5~	$f_6$ ~f_6~	$f_7$ ~f_7~
无	$1$ ~1~	$0$ ~0~	$0$ ~0~	$0$ ~0~	$0$ ~0~	$0$ ~0~	$0$ ~0~	$0$ ~0~
$1$ ~1~	$1$ ~1~	$1$ ~1~	$1$ ~1~	$1$ ~1~	$1$ ~1~	$1$ ~1~	$1$ ~1~	$1$ ~1~
$1, 2$ ~1, 2~	$1$ ~1~	$1$ ~1~	$2$ ~2~	$2$ ~2~	$3$ ~3~	$3$ ~3~	$4$ ~4~	$4$ ~4~
$1, 2, 3$ ~1, 2, 3~	$1$ ~1~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$4$ ~4~	$5$ ~5~	$7$ ~7~	$8$ ~8~
$1 \sim 4$ ~1 \sim 4~	$1$ ~1~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$5$ ~5~	$6$ ~6~	$9$ ~9~	$11$ ~11~
$1 \sim 5$ ~1 \sim 5~	$1$ ~1~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$5$ ~5~	$7$ ~7~	$10$ ~10~	$13$ ~13~
$1 \sim 6$ ~1 \sim 6~	$1$ ~1~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$5$ ~5~	$7$ ~7~	$11$ ~11~	$14$ ~14~
$1 \sim 7$ ~1 \sim 7~	$1$ ~1~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$5$ ~5~	$7$ ~7~	$11$ ~11~	$15$ ~15~

看 $i = 2$ ~i = 2~ 那一行： $f_4$ ~f_4~ 从 $1$ ~1~ 涨到 $3$ ~3~，新增的两个方案正是 $2+2$ ~2+2~ 与 $2+1+1$ ~2+1+1~。能这样使用两遍加数 $2$ ~2~，靠的就是 $j$ ~j~ 从小到大枚举，让 $f_4$ ~f_4~ 读到本轮刚刚更新过的 $f_2 = 2$ ~f_2 = 2~。

最后一行给出 $f_7 = 15$ ~f_7 = 15~，减掉「 $7$ ~7~ 单独成拆」这一种，答案就是 $14$ ~14~。

算法步骤

读入一个整数 $N$ ~N~。
开辟长度为 $N+1$ ~N+1~ 的 64 位数组 $f$ ~f~，全部初始化为 $0$ ~0~，再令 $f_0 = 1$ ~f_0 = 1~。
外层循环枚举加数 $i = 1, 2, \ldots, N$ ~i = 1, 2, \ldots, N~。
内层循环枚举容量 $j = i, i+1, \ldots, N$ ~j = i, i+1, \ldots, N~，执行转移 $f_j \leftarrow (f_j + f_{j-i}) \bmod 2147483648$ 。 $j$ ~j~ 递增枚举，保证同一个加数可以重复使用。
输出 $(f_N - 1 + 2147483648) \bmod 2147483648$ ，即去掉「 $N$ ~N~ 单独成拆」的那一种方案。

复杂度分析

时间复杂度： $O(N^2)$ ~O(N^2)~。外层 $N$ ~N~ 轮，内层平均约 $N/2$ ~N/2~ 次转移， $N = 4000$ ~N = 4000~ 时约为 $8 \times 10^6$ ~8 \times 10^6~ 次加法取模，在 $1$ ~1~ 秒的时限内绰绰有余。
空间复杂度： $O(N)$ ~O(N)~。只需要一个长度为 $N+1$ ~N+1~ 的 64 位数组， $N = 4000$ ~N = 4000~ 时约 $32$ ~32~ 千字节，远小于 $512$ ~512~ 兆字节的内存限制。

实现注意事项

模数超出了 32 位有符号整数的范围。 $2147483648 = 2^{31}$ ~2147483648 = 2^{31}~ 比 int 的上限 $2147483647$ ~2147483647~ 大 $1$ ~1~，所以 $f$ ~f~ 数组与所有中间结果都必须用 64 位整数（C++ 用 long long）。用 int 保存会在 $N$ ~N~ 稍大时溢出成负数。
内层循环必须从小到大枚举 $j$ ~j~，也就是完全背包的写法。若从大到小枚举，同一个加数至多使用一次，得到的是「加数互不相同」的方案数，答案偏小。
每次加法后立即取模，不能攒到最后一次性取模。两个小于模数的数相加不超过 $2 \times (2^{31} - 1)$ ~2 \times (2^{31} - 1)~，小于 $2^{32}$ ~2^{32}~，64 位加法不会溢出；但若不及时取模， $f_j$ ~f_j~ 会迅速膨胀成巨大的整数。由于模数是 $2$ ~2~ 的幂，此处也可以用按位与 & 2147483647 或一次条件减法 if (f[j] >= MOD) f[j] -= MOD; 代替取模。
输出前必须减一。要写成 $(f_N - 1 + MOD) \bmod MOD$ ~(f_N - 1 + MOD) \bmod MOD~，而不是先减再取模，否则 $f_N = 0$ ~f_N = 0~ 时输出会变成负数。
注意 $N = 1$ ~N = 1~ 的边界： $1$ ~1~ 无法拆成至少两个正整数之和，答案应为 $0$ ~0~，程序必须正常输出 $0$ ~0~。
外层 $i$ ~i~ 枚举到 $N$ ~N~ 即可，内层从 $j = i$ ~j = i~ 开始；输入只有一个整数，直接读入 $N$ ~N~ 就能开始计算。

源代码

#include <cstdio>
#include <vector>

// 完全背包：f[j] 表示把 j 拆成若干正整数之和（不计顺序）的方案数。
// 依次把加数 i = 1..N 放进可选集合，每个 i 可以取任意多份，
// 所以内层容量 j 必须从小到大枚举。
const long long MOD = 2147483648LL;   // 2^31，超过 int 的范围，必须用 64 位

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    std::vector<long long> f(n + 1, 0);
    f[0] = 1;                          // 空拆分是递推的基底

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            f[j] = (f[j] + f[j - i]) % MOD;   // f[j] 与 f[j-i] 都小于 MOD，和不超过 2^32
        }
    }

    // f[n] 含「n 自己单独成拆」这一种，题目要求至少 2 个数，减掉它
    long long ans = (f[n] - 1 + MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}

import sys

MOD = 2147483648          # 2^31，超过 32 位有符号整数的上限；Python 的整数不会溢出


def main():
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])

    # f[j]：把 j 拆成若干正整数之和（不计顺序）的方案数，完全背包
    f = [0] * (n + 1)
    f[0] = 1
    for i in range(1, n + 1):
        for j in range(i, n + 1):      # j 从小到大，保证加数 i 可以重复使用
            f[j] = (f[j] + f[j - i]) % MOD

    # 去掉「n 自己单独成拆」这一种；Python 对负数取模仍得非负余数
    print((f[n] - 1) % MOD)


main()

目前没有评论。