題目描述

已知?nn?個整數(shù)?x_1,x_2,\cdots,x_nx1?,x2?,?,xn?，以及?11?個整數(shù)?kk（k<nk<n）。從?nn?個整數(shù)中任選?kk?個整數(shù)相加，可分別得到一系列的和。例如當(dāng)?n=4n=4，k=3k=3，44?個整數(shù)分別為?3,7,12,193,7,12,19?時，可得全部的組合與它們的和為：

3+7+12=223+7+12=22

3+7+19=293+7+19=29

7+12+19=387+12+19=38

3+12+19=343+12+19=34

現(xiàn)在，要求你計(jì)算出和為素數(shù)共有多少種。

例如上例，只有一種的和為素數(shù)：3+7+19=293+7+19=29。

輸入格式

第一行兩個空格隔開的整數(shù)?n,kn,k（1 \le n \le 201≤n≤20，k<nk<n）。

第二行?nn?個整數(shù)，分別為?x_1,x_2,\cdots,x_nx1?,x2?,?,xn?（1 \le x_i \le 5\times 10^61≤xi?≤5×106）。

輸出格式

輸出一個整數(shù)，表示種類數(shù)。

輸入輸出樣例

輸入 #1復(fù)制

4 3
3 7 12 19

輸出 #1復(fù)制

1

說明/提示

【題目來源】

NOIP 2002 普及組第二題

完整代碼如下：

#include<bits/stdc++.h>
using namespace std;
const int N=22;
int a[N],b[N];
int n,m;
int cnt=0;
bool prime(int x){if(x<=1){return false;}for(int i=2;i<=sqrt(x);i++){if(x%i==0){return false;}}return true;
}
void dfs(int k){if(k==m+1){int s=0;for(int i=1;i<=m;i++){s+=a[b[i]];}if(prime(s)){cnt++;}return;}int index=b[k-1];for(int i=index+1;i<=n;i++){b[k]=i;dfs(k+1);}
}
int main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}dfs(1);cout<<cnt<<endl;return 0; 
}