用c++代码写已知 � n 个整数 � 1 , � 2 , ⋯ , � � x 1 ​ ,x 2 ​ ,⋯,x n ​ ，以及 1 1 个整数 � k（ � < � k<n）。从 � n 个整数中任选 � k 个整数相加，可分别得到一系列的和。例如当 � = 4 n=4， � = 3 k=3， 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 时，可得全部的组合与它们的和为： 3 + 7 + 12 = 22 3+7+12=22 3 + 7 + 19 = 29 3+7+19=29 7 + 12 + 19 = 38 7+12+19=38 3 + 12 + 19 = 34 3+12+19=34 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数： 3 + 7 + 19 = 29 3+7+19=29。 输入格式 第一行两个空格隔开的整数 � , � n,k（ 1 ≤ � ≤ 20 1≤n≤20， � < � k<n）。 第二行 � n 个整数，分别为 � 1 , � 2 , ⋯ , � � x 1 ​ ,x 2 ​ ,⋯,x n ​ （ 1 ≤ � � ≤ 5 × 1 0 6 1≤x i ​ ≤5×10 6 ）。 输出格式 输出一个整数，表示种类数。

这是一个经典的组合问题，需要枚举所有的选数方案，并计算它们的和，然后判断和是否为素数。

可以使用回溯法来枚举所有的选数方案，对于每个方案，计算它们的和，并判断和是否为素数。如果和为素数，就累加计数器。最终的计数器的值就是答案。

判断一个数是否为素数，可以使用试除法或者 Miller-Rabin 算法等方法。

C 代码如下：

相关问题

用数据结构c++处理：给定 � n个点， � m条边的有向图，对于每个点 � v，求 � ( � ) f(v)表示从点 � v出发能到达的编号最大的点(包括自己在内)。 � , � ≤ 1 0 5 n,m≤10 5 Input Format 第一行有 2 2个整数 � n, � m。 接下来 � m行，每行2个整数 � � , � � u i ​ ,v i ​ ,表示 � � u i ​ 到 � � v i ​ 有一条边。 点用 1 , 2 , ⋯ , � 1,2,⋯,n编号。 Output Format数据结构c++

可以使用邻接表来存储有向图，然后对于每个点，进行一次DFS或BFS遍历，记录能够到达的最大编号的点。

具体实现可以参考以下代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 5;

vector<int> adj[MAXN];
int n, m;
bool visited[MAXN];

// DFS遍历
int dfs(int v) {
    int res = v;
    visited[v] = true;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (!visited[u]) {
            int tmp = dfs(u);
            if (res < tmp) res = tmp;
        }
    }
    return res;
}

// BFS遍历
int bfs(int v) {
    int res = v;
    queue<int> q;
    q.push(v);
    visited[v] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++) {
            int w = adj[u][i];
            if (!visited[w]) {
                visited[w] = true;
                q.push(w);
                if (res < w) res = w;
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int v = 1; v <= n; v++) {
        // 初始化visited数组
        for (int i = 1; i <= n; i++) visited[i] = false;
        // DFS或BFS遍历
        int max_id = dfs(v); // or bfs(v)
        cout << max_id << endl;
    }
    return 0;
}

不用STL，并尽可能提高算法效率：Description 此题是上一道题目的数据加强版。 给定 � n个点， � m条边的有向图，对于每个点 � v，求 � ( � ) f(v)表示从点 � v出发能到达的编号最大的点(包括自己在内)。 � , � ≤ 1 0 5 n,m≤10 5 Input Format 第一行有 2 2个整数 � n, � m。 接下来 � m行，每行2个整数 � � , � � u i ​ ,v i ​ ,表示 � � u i ​ 到 � � v i ​ 有一条边。 点用 1 , 2 , ⋯ , � 1,2,⋯,n编号。 Output Format � n个整数 � ( 1 ) , � ( 2 ) , ⋯ , � ( � ) f(1),f(2),⋯,f(n).

好的，下面是不使用STL并尽可能提高算法效率的实现方法。

思路：

我们可以使用邻接表存储图，并使用数组记录从每个点出发能到达的编号最大的点。然后从后向前遍历每个点，利用已经计算出来的结果来更新当前点能到达的编号最大的点。

具体实现：

我们可以定义两个数组，一个用来存储图的邻接表，另一个用来记录从每个点出发能到达的编号最大的点。我们可以使用一个指针数组来实现邻接表，指针数组的每个元素是一个指向链表的指针，链表中存储每个点能够到达的下一个点的编号。同时，我们也需要定义一个数组，用来记录从每个点出发能够到达的最大点的编号，一开始可以将这个数组中的每个元素都设置为当前点的编号。

接下来，我们从后向前遍历每个点，对于每个点，我们遍历它能到达的所有点，并将它们的最大编号更新为当前点的最大编号。这样，当遍历完所有点后，我们就能得到每个点出发能到达的编号最大的点了。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;

// 邻接表中存储从当前点能够到达的下一个点的编号
// next[i]表示从i出发能够到达的下一个点的编号
int next[N], head[N], idx;

// maxn[i]表示从i出发能够到达的最大点的编号
int maxn[N];

// 添加一条有向边
void add(int a, int b){
    next[idx] = head[a];
    head[a] = idx++;
}

int main(){
    int n, m;
    cin >> n >> m;

    // 初始化maxn数组
    for(int i = 1; i <= n; i++){
        maxn[i] = i;
    }

    // 建图
    while(m--){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    // 从后向前遍历每个点
    for(int i = n; i > 0; i--){
        // 遍历当前点能到达的所有点
        for(int j = head[i]; j != -1; j = next[j]){
            int v = next[j];

            // 更新从当前点出发能够到达的最大点的编号
            maxn[i] = max(maxn[i], maxn[v]);
        }
    }

    // 输出结果
    for(int i = 1; i <= n; i++){
        cout << maxn[i] << " ";
    }
    cout << endl;

    return 0;
}

时间复杂度：

在这个实现方法中，我们只需要遍历每个点一次，对于每个点，我们需要遍历它能到达的所有点，并更新它们的最大编号。因此，总时间复杂度为 $\mathcal{O}(m+n)$，其中 $m$ 表示边数，$n$ 表示点数。