[NOIP 2002 普及组] 选数

形式化题目

给定集合 $X=\{x_1,x_2,\dots,x_n\}$ 和一个整数 $k$ ，从 $X$ 中任选 $k$ 个数求和。求有多少种选择方案，使得所选数字之和是一个素数。两种选择若包含的数字集合相同，视为同一种方案。

思路

先看一个可以直接验证想法的朴素解：

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
66
67/**
 * 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-13 13:19
 * update_at: 2026-08-13 13:21
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
/* 每层递归决定第 i 个数选/不选，叶子节点统一检查选了 k 个且和为素数。 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, k;
int a[MAXN];      // 输入数组
int choose[MAXN]; // choose[i] = 1 表示选了第 i 个数
int ans;

// 判断 x 是否为素数：只需试除到 sqrt(x)
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

// 检查当前完整 choose[1..n]：选了恰好 k 个且和为素数
void check() {
    int cnt = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i]) {
            cnt++;
            sum += a[i];
        }
    }
    if (cnt == k && is_prime(sum)) ans++;
}

// dfs(dep)：正在决定第 dep 个数的选择（0 不选，1 选）
void dfs(int dep) {
    if (dep == n + 1) {
        check(); // 一条完整 01 序列生成完毕，在叶子节点统一检查
        return;
    }

    // 这一层枚举第 dep 个数的 01 选择
    for (int x = 0; x <= 1; x++) {
        choose[dep] = x;
        dfs(dep + 1);
    }
}

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs(1); // 从第 1 个数开始做选择
    cout << ans << "\n";
    return 0;
}

这个暴力把问题看成一串 01 选择：choose[i] = 0/1 表示第 i 个数不选或选。递归先生成完整的 choose[]，到叶子节点再检查是否恰好选了 $k$ 个、和是否为素数。这种写法要枚举全部 $2^n$ 个子集，其中大量序列根本不满足“选 $k$ 个”的要求，是枚举对象的浪费。

关键观察是组合不关心顺序，下标递增可以天然去重：规定“每次新选的下标必须大于上一次选的下标”，那么每个 $k$ 元集合只会按下标升序出现一次，既不重复也不遗漏。

于是主解直接用组合枚举 DFS：dfs(dep, last, sum) 表示正在选第 dep 个数、上一个选中下标是 last、当前和为 sum；每层枚举下标 $i$ 从 last + 1 到 $n-(k-dep)$ （上界保证后面还能选满 $k$ 个），选满 $k$ 个时用试除法判断 sum 是否为素数并计数。这正好把全部 $\binom{n}{k}$ 个组合生成一遍， $n \leqslant 20$ 时最多 $\binom{20}{10}=184756$ 个，规模很小。

样例搜索树

这张图展示样例 $n=4,k=3$ 时递增下标 DFS 的完整分支过程，叶子标注组合与和：

text

1
2
3
4
5
6
7
8
9
10dfs(1, 0, 0)                            上界 i ≤ n-(k-1) = 2
├─ i=1 (选 3) → dfs(2, 1, 3)            上界 i ≤ 3
│   ├─ i=2 (选 7) → dfs(3, 2, 10)       上界 i ≤ 4
│   │   ├─ i=3 (选 12) → 组合和 22      合数
│   │   └─ i=4 (选 19) → 组合和 29      素数 ✓
│   └─ i=3 (选 12) → dfs(3, 3, 15)      上界 i ≤ 4
│       └─ i=4 (选 19) → 组合和 34      合数
└─ i=2 (选 7) → dfs(2, 2, 7)            上界 i ≤ 3
    └─ i=3 (选 12) → dfs(3, 3, 19)      上界 i ≤ 4
        └─ i=4 (选 19) → 组合和 38      合数

观察要点：每条路径的下标都严格递增，所以 $[3,7,12]$ 只会出现一次、绝不会出现 $[7,3,12]$ ；第一层只枚举到 $i=2$ ，因为选了 3 号或 4 号后剩余下标凑不满 $k=3$ 个，这类分支被上界直接剪掉。四片叶子正好对应全部 4 个组合，其中只有 $3+7+19=29$ 是素数。

代码

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/**
 * 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-13 13:19
 * update_at: 2026-08-13 13:21
 */
/* P1036 [NOIP 2002 普及组] 选数 */
/* 递增下标 DFS 枚举所有选 k 个数的组合，求和并判断是否为素数。 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, k;
int a[MAXN]; // 输入数组
int ans;     // 和为素数的组合个数

// 判断 x 是否为素数：只需试除到 sqrt(x)
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

// dfs(dep, last, sum)：正在选第 dep 个数（从 1 开始），
// 上一个选中的下标是 last，当前已选数字的和是 sum
void dfs(int dep, int last, int sum) {
    if (dep == k + 1) {
        // 已经选满 k 个数，判断和是否为素数
        if (is_prime(sum)) ans++;
        return;
    }

    // 下标递增去重：第 dep 个数只能从 last+1 往后选。
    // 上界剪枝：之后还要选 k - dep 个数，下标 i 最多到 n - (k - dep)
    for (int i = last + 1; i <= n - (k - dep); i++) {
        dfs(dep + 1, i, sum + a[i]);
    }
}

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs(1, 0, 0); // 正在选第 1 个数，上一个下标是 0，当前和为 0
    cout << ans << "\n";
    return 0;
}

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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/**
 * 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-14 14:55
 * update_at: 2026-08-14 14:55
 */
#include <iostream>

const int max_n = 25;

int n, k;
int a[max_n];      // 输入的数字，下标从 1 开始
int chosen[max_n]; // chosen[i] = 1 表示第 i 个数已被选中
int answer = 0;

// x 是素数当且仅当 2..sqrt(x) 都除不尽它
bool is_prime(int x) {
    if (x < 2) {
        return false;
    }
    for (int i = 2; i * i <= x; i += 1) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

// dep: 已经选了几个数；last: 上一个选中的下标；sum: 已选数字的和
void pick(int dep, int last, int sum) {
    if (dep == k) {
        // 选满 k 个数，判断和是否为素数
        if (is_prime(sum)) {
            answer += 1;
        }
        return;
    }
    // 新选的下标必须比 last 大，每个组合只会出现一次；
    // 上界 n - (k - dep) + 1 保证后面还能选满 k - dep 个数
    for (int i = last + 1; i <= n - (k - dep) + 1; i += 1) {
        chosen[i] = 1;
        pick(dep + 1, i, sum + a[i]);
        chosen[i] = 0;  // 回溯恢复，别的组合才能复用这个下标
    }
}

int main() {
    std::cin >> n >> k;
    for (int i = 1; i <= n; i += 1) {
        std::cin >> a[i];
    }
    pick(0, 0, 0);
    std::cout << answer << '\n';
    return 0;
}

复杂度

时间：组合枚举生成 $\binom{n}{k}$ 个组合，每个组合做一次 $O(\sqrt{S})$ 的试除判断（ $S \leqslant k \times 5\times 10^6 \leqslant 10^8$ ， $\sqrt{S} \leqslant 10^4$ ），总 $O\left(\binom{n}{k}\sqrt{S}\right)$ ；实际试除遇到小因子会提前退出，常数很小。
空间： $O(n+k)$ ，递归栈深度至多 $k+1$ 层。

总结

本题是“选 $k$ 个不重复元素 + 判断性质”的经典模板：组合枚举用下标递增这一个约束同时解决去重与剪枝，比 01 序列枚举更贴近组合语义；判素数只需试除到 $\sqrt{x}$ 。rbook 的《组合枚举》讲解了同一种递增下标 DFS（模板 combination），本解即由该模板改造而来。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素想法（brute.cpp）
  01 序列枚举：choose[i] = 0/1，生成全部 2^n 个子集
  叶子统一检查：恰好选 k 个 且 和为素数
        |
        | 瓶颈：枚举对象是 2^n 个子集，多数不是 k 元集合
        v
关键观察
  组合不关心顺序；下标递增 ⇒ 每个 k 元集合只出现一次
  选满 k 个还需 k-dep 个数 ⇒ 循环上界 n-(k-dep)
        |
        v
组合枚举 DFS（main.cpp）
  dfs(dep, last, sum)：正在选第 dep 个数
  i 从 last+1 枚举到 n-(k-dep)，不重不漏且必能选满
  选满 k 个 → is_prime(sum) 试除法计数
        |
        v
复杂度 O(C(n,k) * sqrt(S))，空间 O(n+k)

图中三条主线分别对应“暴力在哪里慢”“观察到什么性质”“正式解如何利用这个性质”。组合枚举的核心是把“恰好选 $k$ 个”写进递归结构本身：每层只枚举大于 last 的下标，且上界保证之后一定能选满，枚举数量从 $2^n$ 收缩到 $\binom{n}{k}$ 。