题目链接:https://ac.nowcoder.com/acm/contest/230/B
题目大意:
略
分析:
DFS模板题。
代码如下:
#include <bits/stdc++.h>
using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a)) #define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
const int maxN = 1e5 + ; int n, k, ans;
int x[]; bool isPrime(int x) {
assert(x > );
For(i, , (int)(sqrt(x) + 1e-)){
if(x % i == ) return false;
}
return true;
} void dfs(int a, int cnt, int sum) {
if(cnt == k) {
if(isPrime(sum)) ++ans;
return;
}
if(a > n) return; dfs(a+, cnt+, sum+x[a]);
dfs(a+, cnt, sum);
} int main(){
scanf("%d%d", &n, &k);
For(i, , n) x[i] = ri(); dfs(, , ); printf("%d\n", ans);
return ;
}