https://www.luogu.org/problemnew/show/P1036
$n$ 才20的数据量，我当时居然还在想怎么分组组合，直接 $2^{20}$ 暴力搞就行了。
$x_i $太大了，不能事先处理出所有素数。误！多数了一个0！但是一共和的结果最多和选法的次数一样，$2^{20}$，也就是 $10^{6}$（好像也很多），验证是素数要$10^{4}$……
原来看错了！那就用埃筛然后暴力判断就好了。
暴力都写了半天，关键在于要在dfs进入的时候立刻处理选择才对。
#include<bits/stdc++.h>
using namespace std;
#define ll long long int num[];
int p[];
int ptop=; int ans=; void init(){
num[]=;
num[]=;
for(int i=;i<=;i++){
if(num[i]==){
p[ptop++]=i;
for(int j=i+i;j<=;j+=i)
num[j]=;
}
}
/*for(int i=0;i<ptop;i++)
printf("%d ",p[i]); printf("\n");*/
} int n,k;
int a[];
void dfs(int i,int c,int curk,int sum){
if(curk<)
return;
if(i==n){
if(c==&&curk==){
//cout<<sum<<endl;
if(num[sum]==){
//cout<<sum<<endl;
ans++;
}
}
}
else{
if(c==){
dfs(i+,,curk,sum);
dfs(i+,,curk-,sum);
}
else{
sum+=a[i];
dfs(i+,,curk,sum);
dfs(i+,,curk-,sum); }
}
} int main(){
init();
scanf("%d%d",&n,&k);
for(int i=;i<n;i++){
scanf("%d",&a[i]);
} dfs(,,k,);
dfs(,,k-,); printf("%d\n",ans);
}