选数题解【高强度样例最快】

时间复杂度：$O(C(n,k)*\sqrt{S})$
$S$为$k$个数加起来的$max$
将质数为偶数的情况排掉，大的数判断能否质因数分解，再使用记忆化来优化，然后加上剪枝和输入优化。(洛谷 $hack$ 仅用$10ms$)

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
int a[30];
unordered_map<int,bool> prime_cache;
const int small_primes[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
bool check(int x){
    if(prime_cache.count(x))return prime_cache[x];
    bool res=true;
    if(x<2)res=false;
    else if(x%2==0)res=(x==2);
    else{
        for(int p:small_primes){
            if(p>x/p)break;
            if(x%p==0){
                res=false;
                break;
            }
        }
        if(res){
            for(int i=101;i<=x/i;i+=2){
                if(x%i==0){
                    res=false;
                    break;
                }
            }
        }
    }
    prime_cache[x]=res;
    return res;
}
void dfs(int start,int sum,int cnt){
    if(cnt==k){
        if(sum%2==0&&sum>2)return;
        ans+=check(sum);
        return;
    }
    if(cnt>k||start==n+1||cnt+(n-start+1)<k)return;
    dfs(start+1,sum+a[start],cnt+1);
    dfs(start+1,sum,cnt);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,0,0);
    cout<<ans;
    return 0;
}