A+B Problem（再升级）

题意

给定一个正整数 n，求把它分解成若干个素数之和的方案总数。

这里"方案总数"指的是组合数，不是排列数。

例如 7 的方案有：

7
2 + 5
2 + 2 + 3

所以答案是 3。

这张表把题目翻译成了背包模型：

原题对象	背包含义
一个素数	一个可以重复使用的物品
选择一个素数	目标和增加这个素数
目标	凑出总和 `n`
评价标准	方案数累计

从这里可以看出，本题是"组合计数版"的完全背包。

思路

一句话本质：筛出所有 ≤ n 的素数作为可无限使用的物品，用完全背包计数——外层枚举素数、内层正序容量，自然保证统计的是组合而不是排列。

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。

const int MAXN = 1005;

int n;
bool is_prime[MAXN];
vector<int> primes;
vector<int> choose_count; // choose_count[i] 表示第 i 个素数用了多少次
long long answer;

void build_primes() {
    for (int i = 2; i <= n; i++) {
        if (!is_prime[i]) {
            primes.push_back(i);
            for (int j = i + i; j <= n; j += i) {
                is_prime[j] = true;
            }
        }
    }
}

int calc_sum() {
    int sum = 0;
    for (int i = 0; i < (int)primes.size(); i++) {
        sum += choose_count[i] * primes[i];
    }
    return sum;
}

// 依次枚举每个素数用了多少次，最后统一检查总和。
void dfs_choose(int dep) {
    if (dep == (int)primes.size()) {
        if (calc_sum() == n) {
            answer++;
        }
        return;
    }

    int p = primes[dep];
    int limit = n / p;
    for (int cnt = 0; cnt <= limit; cnt++) {
        choose_count[dep] = cnt;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    build_primes();
    choose_count.assign(primes.size(), 0);
    dfs_choose(0);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每个素数用了多少次看成一层选择：choose_count[i] 表示第 i 个素数使用次数。递归先生成完整计数序列，叶子节点再检查能不能刚好凑出 n。

这个做法显然正确，但复杂度很高，只适合小数据验证。

题目要求统计"组合数"而非"排列数"，背包计数怎么保证这一点？

关键在于外层枚举物品（素数），内层枚举容量（目标值）。当处理素数 p 时，dp[j] += dp[j - p] 把所有"末尾是 p"的方案一次性计入。因为 p 只在外层出现一次，所有含 p 的方案只按一种顺序被统计，天然去除了 2+5 和 5+2 这种不同排列的重复计数。

如果反过来（外层容量、内层物品）会怎样？

那就会把不同顺序的方案都当独立的方案计数，例如 2+5 和 5+2 各算一次。这不符合题意要求的组合计数。

完全背包计数和普通完全背包的区别？

转移从 max 变成累加：dp[j] += dp[j - p]。dp[0] = 1 表示"凑出 0 有且仅有一种方法：什么都不选"。正序枚举让每个素数可重复使用；外层枚举素数保证组合性质。

状态表

这张表说明状态定义：

状态	含义
`dp[j]`	凑出 `j` 的组合方案数

初始化时：

dp[0] = 1

表示凑出 0 有一种方法：什么都不选。

处理一个素数 p 时，完全背包正序枚举：

dp[j] += dp[j - p]

这里正序枚举会让同一种素数在本轮继续参与转移，符合"可以重复使用"的要求。

同时因为外层是素数，内层是容量，所以同一个组合只会按固定顺序统计一次，不会把 2+5 和 5+2 当成两个方案。

最后输出 dp[n] 即可。

DP 公式

设 $dp_j$ 表示凑出 $j$ 的组合方案数。初始化：

dp_0=1

对每个素数 $p$ 做完全背包计数：

dp_j\leftarrow dp_j+dp_{j-p}

其中 $j\geqslant p$ 且容量正序枚举。最终答案为：

dp_n

公式解释：外层枚举素数，内层正序枚举和，可以保证统计的是组合而不是排列。dp_{j-p} 的每种方案加上一个素数 p，都会变成凑出 j 的方案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:13
 * update_at: 2026-08-08 23:13
 * 筛素数 + 完全背包计数
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1005;
int n;
bool is_prime[maxn];
vector<int> primes;
ll dp[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    dp[0] = 1;
    for (int p : primes)
        for (int j = p; j <= n; ++j)
            dp[j] += dp[j - p];
    cout << dp[n] << "\n";
    return 0;
}

复杂度

时间复杂度： $O(n \pi(n))$
空间复杂度： $O(n)$

总结

这题是完全背包的计数版本：

每个素数可以重复选
统计的是组合数，不是排列数
状态转移是累加方案数

以后看到"无限次选取 + 统计方案数"这类条件时，就可以优先往完全背包上想。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。