题解 | #[NOIP2002]选数#

全排列+素数判定
直接枚举
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[30],book[21];//a数组保存，book标记
int c[21],s;
bool ss(int x)//素数函数
{
    if(x<2)
        return false;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return false;
    return true;
}
void dfs(int step)//全排列模板
{
	if(step==k+1)//判定保存数据是否通过
	{
		for(int i=1;i<=k;i++)
			if(c[i]<c[i-1])//去重
				return ;
        int ans=0;
		for(int i=1;i<=k;i++)
            ans+=a[c[i]];
        if(ss(ans))//判定是否是素数
            s++;
		return ;
	}
    for(int i=1;i<=n;i++)
    {
   		if(book[i]==0)//搜索+回溯
		{
			c[step]=i,book[i]=1;
			dfs(step+1);
			book[i]=0;
		}
	}
}
int main() 
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];//输入
    dfs(1);
    cout<<s<<endl;
}