Noip 2002 popularity group selection number

subject

Topic link
Brief description of the topic ：
Description
It is known that n It's an integer x1,x2,…,xn, And an integer k（k＜n）. from n Any number of integers k Add the whole numbers , We can get a series of and respectively . For example, when n=4,k＝3,4 The integers are 3,7,12,19 when , All the combinations and their sum can be obtained as ：
3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34.
Now? , Ask you to work out how many kinds of sum are prime numbers .
For example, the above example , There is only one sum of prime numbers ：3＋7＋19＝29）.

Input
Keyboard entry , The format is ：
n , k （1<=n<=20,k＜n）
x1,x2,…,xn （1<=xi<=5000000）

Output
Screen output , The format is ：
An integer （ The number of species that satisfy the condition ）.
Sample Input

4 3
3 7 12 19

Sample Output

1

Ideas

1. This type of topic is combinatorial enumeration , The corresponding traversal method is DFS + prune
2. DFS stay n Selected from the number k Number , use chosen preservation , The number of choices exceeds k(chosen.size() > k) Or even if the number has been selected now + All the remaining numbers cannot be equal to k Of DFS Pruning (chosen.size() + (n - u) < k)
3. use check_valid Function to judge the selected k Whether the number meets the meaning of the question , take chosen Add all the numbers in to get sum, Judge sum Is it a prime , If it's a prime number , The number of types that meet the meaning of the topic cnt ++;

Code

#include <iostream>
#include <vector>

using namespace std;

const int N = 30;

long long q[N]; //  Input array 
int n, k, cnt; // cnt The number of categories required for the topic 
vector<int> chosen; // Store the number selected each time  

bool is_prime(int n) // Prime judgment template  
{
    
	if (n < 2) return false;
	for (int i = 2; i <= n / i; i ++)
		if (n % i == 0) return false;
	return true;
}

bool check_valid(vector<int> a) // Judge whether the sum of the selected numbers is a prime number  
{
    
	long long sum = 0;
	for (int i = 0; i < a.size(); i ++ ) sum += a[i];
	if (is_prime(sum)) 
		return true;
	return false;
}

void dfs(int u)
{
    
	// prune , If you have selected more than m Number , Or even if you reselect all the remaining numbers, it's not enough m individual , You can know in advance that the current problem has no solution  
	if (chosen.size() > k || chosen.size() + (n - u) < k) return; 
	if (u == n) // Boundary situation  
	{
    
		if (check_valid(chosen)) cnt ++; // use check_valid Function to determine whether the selected number meets the requirements  
		return;
	}
	
	dfs(u + 1); // No second choice u Number  
	chosen.push_back(q[u]); //  Choose the first u Number  
	dfs(u + 1);
	chosen.pop_back(); //  to flash back , Restore scene  
}


int main()
{
    
	cin >> n >> k;
	for (int i = 0; i < n; i ++ ) cin >> q[i];
	dfs(0);
	cout << cnt << endl;
	
	return 0;
}