【题目描述】

$n=4$, $=3$, $4$个整数分别为3$,7,12,19$时,可得全部的组合与它们的和为:

3+7+12=22　　 3+7+19=29　　 7+12+19=38　 3+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:(3+7+19=29)。

【输入描述】

        第二行为n个数$x_1{x}_2\dots \dots x_n(1\le x_i\le 5000000)$,各数之间用一个空格隔开)

【输出描述】

        一个整数（满足所有条件的种数）

【样例输入】

4 3   3 7 12 19

【样例输出】

1

【题目分析】

• 用到了判断素数

• 简单的排列是不行的，比如3 7 12 和3 12 7 是两种不同的排列，但是加起来的结论是一样的，所以要进行简单改变

【解法一：利用组合数公式】

如果我们用的DFS把所有可能的排列情况求出来，那么肯定是重复的，既然这样，我们就用组合数公式，可以看出，组合数公式就是排序数除以m的阶乘。那么题目来说就比较简单了。

#include <bits/stdc++.h>  using namespace std;  long long n,k,sum,cnt,times,flag,a[21],vis[21];  //检测质数   void check(long long sum) {  	flag=0;//clear  	if(sum!=2) {  		for(int i=2; i*i<=sum; i++) {  			if(sum%i==0) {  				flag=1;  				break;  			}  		}  	}  	if(sum==2) flag=0;  	if(flag==0) cnt++;  }  void dfs(long long depth) {  	if(depth==k+1) {  		check(sum);//判断是否是质数   		return;  	}  	for(int i=1; i<=n; i++) {  		if(vis[i]!=1) {  			vis[i]=1;  //标记被使用过了   			sum+=a[i];  //把使用过的数加起来   			dfs(depth+1); //深搜下一个   			sum-=a[i];  			vis[i]=0;  //回溯一步   		}  	}  }  int main() {  	cin>>n>>k;//读入n和k   	for(int i=1; i<=n; i++)  		cin>>a[i];  	dfs(1);  	times=1;  //阶乘  	for(int i=1; i<=k; i++)   		times*=i;  	cout<<cnt/times<<endl;  	return 0;  }

【解法二：利用单调性筛选】

我们不能直接用DFS的方法，是因为有重复的数据，只要我们保证我们产生的数据没有重复的，就OK了。

比如，我们4选3。比较好的写法应该是

1 2 3   1 2 4  1 3 4  2 3 4

那么我们只要保证在全排列的时候，后面的数比前面的大就能作出组合数了。

(adsbygoogle = window.adsbygoogle || []).push({});