洛谷：P1036：选数

题目

P1036：选数

分析

通过分析题意，我们要先知道一点：加法是符合交换律的：\(a+b=b+a\)。因此，这个问题的核心是\(C_n^k\)的问题：如何在n个数中挑出k个数。至于求和并判断是否质数的问题，就很常规了。

C++中有内置的next_permutation函数，但是它用来得到排列而不是组合，而且它是全排列，也就是在n个元素中选出n个元素的排列，和题意还是有一点差异的。

我们考虑一下产生组合的过程，并用下表来模拟一下（假定有4个元素，并从中选择3个组合，0表示不选，1表示选）：

元素	1	2	3	4	结果
选择0	0	0	0	0	0000
选择1	0	0	0	1	0001
选择2	0	0	0	0	0010
... ...	... ...	... ...	... ...	... ...	... ...
选择15	1	1	1	1	1111

组合的总数一定是\(2^n\)个，编号从\(0\)到\(2^n-1\)，而且用n位2进制来表示该编号的话，各位的0/1就表示了该对应位的元素是否被选。

当然，所有的组合中只有部分是符合条件的，因为只能选k个元素，我们需要对一个数字统计它用2进制表示时，有几个1。这个不难：

    int count = 0;
    while (num)
    {
        num &= (num - 1);
        count++;
    }
    return count;

然后，如果这个数确实有k个1，那么就挑出对应1位置的元素，这个可以用&来挑选：

if (mask & (1 << i))
{
  sum += nums[i];
}

最后，判断一下这个数是不是质数即可。

答案

思考

非常有意思的一道题目！一道看似和排列组合无关的数论题目，在掌握了2进制、位运算之后，可以借助这些基本语法完成！

另外的解法

在DFS章节，这道题又出现了，不过要求用DFS解决。这也是可以的。

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int num)
{
    if (num <= 1)
        return false;
    if (num == 2)
        return true;
    if (num % 2 == 0)
        return false;
    for (int i = 3; i <= sqrt(num); i += 2)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

int n, k;
vector<int> nums;
int count = 0;

void dfs(int pos, int selected, int sum)
{
    // 已经选择了k个数
    if (selected == k)
    {
        if (isPrime(sum))
        {
            count++;
        }
        return;
    }

    // 剩余的数不够凑齐k个
    if (n - pos < k - selected)
        return;

    // 选择当前位置的数
    if (pos < n)
    {
        dfs(pos + 1, selected + 1, sum + nums[pos]);
        // 不选择当前位置的数
        dfs(pos + 1, selected, sum);
    }
}

int main()
{
    cin >> n >> k;
    nums.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    dfs(0, 0, 0);
    cout << count << endl;

    return 0;
}