【正经题解】第一篇 选数 dfs+状压

各位大佬们，蒟蒻们，大家好！
由于这是我的第一篇题解，所以请大家给我点个赞！谢谢！
如果想，可以进入我们学生党团
正片开始：

蒟蒻版：dfs.
众所周知，dfs的理念是一战到底。
所以我们利用dfs思想，记录数量，位置，总和，如果达到数量，就判断和是否为素数
本网站介绍了四种判断素数方法，不会的可以学一学
好了，dfs就讲到这里，直接华丽上代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
bool pr(long long s){
    for(long long i=2;i*i<=s;i++){
    //如果i*i超出long long范围，就要改成i<=s/i
        if(s%i==0)return 0;
    }
    return 1;
}//普通素数判断
long long ans=0;
int a[25];
void dfs(int i,int h,long long l){
//i为当前位置，h为选择数量，l为总和
    if(h==k){
        if(pr(l)){
            ans++;//记录答案
        }
        return ;
    }
    if(i>n)return ;//n个全遍历完，返回
    dfs(i+1,h+1,l+(long long)a[i]);//选
    dfs(i+1,h,l);//不选
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1,0,0LL);
    cout<<ans<<endl;
}

大佬版（蒟蒻也可以研究一下）：
本题首先要引入一下大名鼎鼎的状态压缩（不一定是dp）
状态压缩又要涉及到二进制和位运算

如果没看懂的话可以看看本网站
利用二进制拆分每一位，计数并求和，再判断素数。
好了，依旧华丽上代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
bool pr(long long s){
    for(long long i=2;i*i<=s;i++){
    //如果i*i超出long long范围，就要改成i<=s/i
        if(s%i==0)return 0;
    }
    return 1;
}//普通素数判断
long long ans=0;//记录答案
int a[25];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    //以下方法对状压dp有极大帮助，当n=20时，时间复杂度O(20,971,520)
    for(int mask=0;mask<(1<<n);mask++){
        //二进制枚举：注意！n>20时不能使用，否则你会得到TLE
        long long l=0,cnt=0;
        for(int i=1;i<=n;i++){
            if((mask>>(i-1))&1){
                l+=a[i];
                cnt++;
            }
        }
        if(cnt!=k)continue;//个数不符合直接舍弃
        if(pr(l)){
            ans++;//如果符合素数，ans直接累加
        }
    }
    cout<<ans<<endl;
}

由于这是我的第一篇题解，所以请大家给我点个赞！谢谢！
管理员大大辛苦，谢谢！
如有问题不要管私信我