[NOIP 2002 普及组] 选数

知识点

组合枚举、深度优先搜索、素数判定

解题思路

深度优先搜索选择位置，每次只从上次之后的位置继续选，选满k个时对总和做试除判素数；剩余元素不够时提前停止。相同数值位于不同下标仍是不同选择。

正确性说明

任意k个下标按递增排序有唯一形式。搜索恰好生成每个递增下标序列一次，所以不重复也不遗漏。对每个组合检查其和的素性，计数即为答案。

易错点

1不是素数；枚举的是组合而非排列；不能按数值去重；n=20而k接近n时仍要正确剪枝。

复杂度

组合数为C(n,k)，时间O(C(n,k)·(k+sqrt(kA)))的保守界，A为元素最大值；递归额外空间O(k)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int n,k;vector<int>a;long long ans=0;
bool prime(int x){if(x<2)return false;if(x%2==0)return x==2;for(int d=3;1LL*d*d<=x;d+=2)if(x%d==0)return false;return true;}
void dfs(int start,int left,int sum){if(!left){ans+=prime(sum);return;}for(int i=start;i<=n-left;++i)dfs(i+1,left-1,sum+a[i]);}
int main(){cin>>n>>k;a.resize(n);for(int&x:a)cin>>x;dfs(0,k,0);cout<<ans<<'\n';}