题目
题解
题目给定 $N$ 个正整数，要求我们从中恰好选出 $K$ 个数，使得这些数的和为质数，最后统计一共有多少种不同的选法。
这里首先需要明确两个概念：
- 必须恰好选择 $K$ 个数，不能多选，也不能少选。
- 不同选法按照选取的下标区分，即使两个位置上的数字相同，只要选取的位置不同，就认为是不同的方案。
例如数组为：
$$
[2,2,3]
$$
当 $K=2$ 时，选择第 $1,3$ 个数与选择第 $2,3$ 个数，虽然得到的和都是 $5$，但仍然属于两种不同方案。
因此，这道题实际上由两个子问题组成：
- 如何枚举恰好选取 $K$ 个数的所有方案？
- 如何判断一个方案的元素和是否为质数？
我们分别解决。
一、如何枚举全部选法？
观察数据范围：
$$
1\le K\le N\le20
$$
由于 $N$ 的最大值只有 $20$，我们可以考虑直接枚举全部选择方案。
对于每个位置上的数，实际上只有两种选择：
- 选取这个数。
- 不选取这个数。
因此，如果不限制必须选取 $K$ 个数，全部可能的选择方案数为：
$$
2^N
$$
当 $N=20$ 时：
$$
2^{20}=1048576
$$
大约有 $100$ 万种方案，这个规模完全可以考虑使用枚举算法。
但是题目只需要恰好选择 $K$ 个数的方案，所以我们可以进一步优化，只枚举符合数量要求的组合。
二、DFS 与组合枚举
这里介绍使用 DFS（深度优先搜索）完成组合枚举的方法。
假设给定数组：
$$
[1,2,3,4]
$$
要求选出恰好 $2$ 个元素，那么所有按照下标区分的选择方案为：
$$
(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)
$$
我们可以观察到一个规律：如果每次都规定新选择的下标必须大于上一次选择的下标，那么就能保证同一组下标不会被重复枚举。
例如选择下标 $1,3$ 之后，我们就不会再枚举 $3,1$，因为二者实际上是同一种选法。
我们不妨定义一个 DFS 函数：
dfs(start, cnt, sum);其中：
start：下一次可以选择的最小下标。cnt：当前已经选取的元素数量。sum：当前选取的所有元素之和。
初始状态显然为：
dfs(1, 0, 0);假设当前选择了下标为 $i$ 的元素，那么下一次只能从 $i+1$ 开始选择，因此递归调用：
dfs(i + 1, cnt + 1, sum + a[i]);当 cnt == K 时，说明已经完成了一种合法数量的选择方案，此时不需要再选择其他元素，直接判断 sum 是否为质数即可。
如果是质数，答案增加 $1$；否则直接结束当前递归分支。
还有一个优化：假设当前已经选择了 cnt 个数，还需要选择 $K-cnt$ 个，而当前剩余可供选择的元素数量不足 $K-cnt$，那么无论怎样继续搜索，都不可能形成合法方案，可以提前结束。
实际上，我们也可以直接限制枚举下标的上界，避免进入这些无意义的分支。
三、如何判断质数？
根据题目定义，质数是大于 $1$，并且只有 $1$ 和自身两个正因数的整数。
例如 $2,3,5,7,11$ 都是质数，而 $1,4,6,8,9$ 都不是质数。
最容易想到的方法是试除法：对于一个整数 $x$，尝试判断是否存在满足以下条件的整数 $i$：
$$
2\le i<x,\qquad x\bmod i=0
$$
如果存在这样的整数，那么 $x$ 就不是质数。
但是，我们并不需要枚举到 $x-1$。
假设 $x$ 是合数，那么必然能够表示为：
$$
x=a\times b
$$
其中 $a,b$ 都是大于 $1$ 的整数。
不妨令 $a\le b$，那么显然：
$$
a^2\le ab=x
$$
因此：
$$
a\le\sqrt{x}
$$
也就是说，如果 $x$ 是合数，那么它一定存在一个不超过 $\sqrt{x}$ 的因数。
所以判断质数只需要枚举：
$$
2\le i\le\sqrt{x}
$$
如果没有找到任何因数，并且 $x>1$，那么 $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;
}这里特别注意，$1$ 不是质数，必须单独判断。
另外，循环条件 i * i <= x 与 i <= sqrt(x) 的含义相同，但是前者不需要使用浮点数运算，更适合本题。
四、时间复杂度分析
我们先计算需要枚举多少种选择方案。
从 $N$ 个位置中选择恰好 $K$ 个位置，组合数为：
$$
\binom{N}{K}=\frac{N!}{K!(N-K)!}
$$
当 $N=20$ 时，组合数的最大值出现在 $K=10$：
$$
\binom{20}{10}=184756
$$
所以我们最多只需要检查不到 $19$ 万种完整的选择方案。
再考虑质数判断。
题目保证：
$$
a_i\le1000
$$
且最多选择 $20$ 个数，因此任意一种方案的元素和都不超过：
$$
20\times1000=20000
$$
每次质数判断最多枚举大约 $\sqrt{20000}$ 个候选因数，计算量完全可以接受。
因此，不需要使用特别复杂的算法，仅通过 DFS 组合枚举与试除法，就足以解决这道题。
五、C++ 代码
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
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;
}
void solve()
{
int n, k; cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
ll ans = 0;
auto dfs = [&](auto&& dfs, int start, int cnt, int sum) -> void
{
if (cnt == k)
{
if (is_prime(sum)) ans++;
return;
}
// 剩余位置必须足够选满 k 个元素
for (int i = start; i <= n - (k - cnt) + 1; ++i)
{
dfs(dfs, i + 1, cnt + 1, sum + a[i]);
}
};
dfs(dfs, 1, 0, 0);
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}六、正确性分析
为了确认 DFS 没有重复枚举或者遗漏合法方案，我们可以从两个方面进行分析。
首先，所有合法方案一定会被枚举到。
对于任意一种合法选法，假设选中的 $K$ 个下标从小到大为：
$$
i_1<i_2<\cdots<i_K
$$
由于 DFS 每次都可以在当前下标之后继续选择，因此一定存在一条搜索路径，依次选择 $i_1,i_2,\ldots,i_K$。
所以全部合法方案都可以被搜索到。
其次，每种合法方案只会被枚举一次。
因为 DFS 规定每次新选择的下标必须严格大于前一个下标，所以同一组位置只能以升序被选择。
因此，不可能出现同一组下标以不同顺序被重复枚举的情况。
当选中元素数量达到 $K$ 时，我们恰好统计一次该方案，并使用正确的质数判断函数检查其元素和。
综上，算法能够恰好统计所有满足条件的选择方案。
七、总结
本题主要考查组合枚举与质数判断。
对于 $N\le20$ 这样的数据范围，我们应当主动考虑枚举或搜索，而不是一看到选取若干元素，就立即想到动态规划。
此外，本题与全排列枚举有一个本质区别：组合不关心选取顺序，因此我们可以要求下标严格递增，从而避免重复枚举。
关于复杂度，令 $A=\max(a_i)$，DFS 的搜索与质数判断总时间复杂度可以写为：
$$
O\left(K\binom{N}{K}+\binom{N}{K}\sqrt{KA}\right)
$$
由于本题 $N\le20$，该复杂度能够满足题目要求。
递归深度最多为 $K$，因此辅助空间复杂度为 $O(N)$。
难度： 普及−（橙，偏上，个人评估）
考点： 组合枚举、DFS、回溯、质数判断、剪枝
时间复杂度： $O\left(K\binom{N}{K}+\binom{N}{K}\sqrt{KA}\right)$
空间复杂度： $O(N)$