https://www.luogu.com.cn/problem/P1036
题目大意：从给定的n个数中选出m个求和，结果是一个素数的情况有多少种？
输入
4 3
3 7 12 19
输出
1
这个题目的代码是根据Acwing中蓝桥杯dfs专题 93.递归实现组合型枚举改动而来
https://www.acwing.com/problem/content/95/
模板如下：
dfs(1,1);
void dfs(int u,int st)
{
_____if(u==m+1) { for(1,m); …… ；return; }
_____for(int i=st;i<=n;i++) { way[i]=a[i]; dfs(u+1,i+1); way[i]=0; }
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL N=200200,M=2002;
const int INF=0x3f3f3f3f;
LL n,m,ans=0;
LL a[N],way[N];
bool is_prime(LL x)
{
if(x<2) return false;
for(LL i=2;i<=x/i;i++)
if(x%i==0) return false;
return true;
}
void dfs(LL u,LL st)
{
if(u==m+1)
{
LL sum=0;
for(LL i=1;i<=m;i++)
sum+=way[i];
if(is_prime(sum)==true) ans++;
return ;
}
for(LL i=st;i<=n;i++)//从当前位置继续往后拼凑
{
way[u]=a[i];
dfs(u+1,i+1);
way[u]=0;//状态回溯
}
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
cin>>n>>m;
for(LL i=1;i<=n;i++)
cin>>a[i];
dfs(1,1);//从第一个位置开始填放，从数组a中的第一个数开始填
cout<<ans<<endl;
}
return 0;
}