python/LuoGu/RuMen/P1036.cpp

#include <bits/stdc++.h>

using namespace std;



/*
    这个register int中的register 表示使用cpu内部寄存器（寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件）的变量，
    而平时的int是把变量放在内存中，存到寄存器中可以加快变量的读写速度 这是一个循环1e8的代码在使用int的用时
    注意一般在多层循环用
*/

/**
 * 功能：判断是不是素数
 * 作者：黄海
 * 时间：2019-11-27
 * @param x
 * @return
 * 注意：inline 内联函数 参考：http://c.biancheng.net/view/199.html
 */
inline bool prime(int x) {
    for (register int i = 2; i <= sqrt(x); i++)
        if (x % i == 0)
            return false;
    return true;
}


int a[10001];  //可以用一个a数组来记录我们所选的数
int n;  // n是所有整数的个数
int k;  // k是选择整数的个数
int total; //total为总方案数
/**
 * 功能：深度优先搜索的主函数
 * 作者：黄海
 * 时间：2019-11-27
 * @param step :记录当前选的是第几个数
 * @param sum  :相加的和是什么
 * @param cnt  :已选的可用的数
 */
inline void dfs(int step, int sum, int cnt) {
    //如果已经进行到了n+1次，或者是已经选了k个数
    if (step == n + 1 || cnt == k) {
        //如果sum为一个素数且已经选了k个数
        if (prime(sum) && cnt == k) {
            total++;  //总方案数+1
        }
        return;
    }
    //继续枚举不选择下一个数的情况
    dfs(step + 1, sum, cnt);

    //继续搜索，选择下一个数
    dfs(step + 1, sum + a[step], cnt + 1);

    return;
}

int main() {
    //读入输出优化的强迫症
    ios::sync_with_stdio(false);
    //输入n和k
    cin >> n >> k;
    //输入数据
    for (register int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //从第1个数开始搜
    dfs(1, 0, 0);
    //输出结果
    cout << total;
    return 0;
}