商业网站的网址,百度做网站不给FTP密码,石河建设技校网站,黑彩网站建设[NOIP2002 普及组] 选数
题目描述
已知 n n n 个整数 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn#xff0c;以及 1 1 1 个整数 k k k#xff08; k n kn kn#xff09;。从 n n n 个整数中任选 k k k 个整数相加#xff0c;可分别得…[NOIP2002 普及组] 选数
题目描述
已知 n n n 个整数 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn以及 1 1 1 个整数 k k k k n kn kn。从 n n n 个整数中任选 k k k 个整数相加可分别得到一系列的和。例如当 n 4 n4 n4 k 3 k3 k3 4 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 3,7,12,19 时可得全部的组合与它们的和为 3 7 12 22 371222 371222 3 7 19 29 371929 371929 7 12 19 38 7121938 7121938 3 12 19 34 3121934 3121934
现在要求你计算出和为素数共有多少种。
例如上例只有一种的和为素数 3 7 19 29 371929 371929。
输入格式
第一行两个空格隔开的整数 n , k n,k n,k 1 ≤ n ≤ 20 1 \le n \le 20 1≤n≤20 k n kn kn。
第二行 n n n 个整数分别为 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn 1 ≤ x i ≤ 5 × 1 0 6 1 \le x_i \le 5\times 10^6 1≤xi≤5×106。
输出格式
输出一个整数表示种类数。
样例 #1
样例输入 #1
4 3
3 7 12 19样例输出 #1
1提示
【题目来源】
NOIP 2002 普及组第二题 在最后的序列中 相同的数不能用第二次 不同的序列不能出现完全一样的数 #includebits/stdc.h
using namespace std;int n,k;
int a[25];
int path[25];
vectorint v;
bool st[25] {false};
int ans;bool isPrime(int q)
{if(q 1)return false;for(int j 2;j*j q;j)//j - j*j{if(q % j 0)return false;}return true;
}void dfs(int u,int start)//start确保每个数字仅在其之后的位置被尝试避免了生成重复的组合
{if(u k){int sum 0;for(int i 0;i k;i){sum sum path[i];}v.push_back(sum);return;}for(int i start;i n;i){if(!st[i]){path[u] a[i];st[i] true;dfs(u1,i1);st[i] false;}}
}int main()
{cin n k;for(int i 0;i n;i){cin a[i];}dfs(0,0);for(vectorint::iterator it v.begin();it!v.end();it){if(isPrime(*it)){ans;}}cout ans endl;return 0;
}
