[NOIP 2002 普及组] 选数

Luogu
IDLGP1036
Time1500ms
Memory128MB
DifficultyP2
搜索2002NOIP 普及组深度优先搜索 DFS素数判断,质数,筛法
已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$,以及 $1$ 个整数 $k$($k<n$)。从 $n$ 个整数中任选 $k$ 个整数相加,可分别得到一系列的和。例如当 $n=4$,$k=3$,$4$ 个整数分别为 $3,7,12,19$ 时,可得全部的组合与它们的和为: $3+7+12=22$ $3+7+19=29$ $7+12+19=38$ $3+12+19=34$ 现在,要求你计算出和为素数共有多少种。 例如上例,只有一种的和为素数:$3+7+19=29$。 ## Input 第一行两个空格隔开的整数 $n,k$($1 \le n \le 20$,$k<n$)。 第二行 $n$ 个整数,分别为 $x_1,x_2,\cdots,x_n$($1 \le x_i \le 5\times 10^6$)。 ## Output 输出一个整数,表示种类数。 [samples] ## Note **【题目来源】** NOIP 2002 普及组第二题
Samples
Input #1
4 3
3 7 12 19
Output #1
1
API Response (JSON)
{
  "problem": {
    "name": "[NOIP 2002 普及组] 选数",
    "description": {
      "content": "已知 $n$ 个整数 $x_1,x_2,\\cdots,x_n$,以及 $1$ 个整数 $k$($k<n$)。从 $n$ 个整数中任选 $k$ 个整数相加,可分别得到一系列的和。例如当 $n=4$,$k=3$,$4$ 个整数分别为 $3,7,12,19$ 时,可得全部的组合与它们的和为: $3+7+12=22$ $3+7+19=29$ $7+12+19=38$ $3+12+19=34$ 现",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1036"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "已知 $n$ 个整数 $x_1,x_2,\\cdots,x_n$,以及 $1$ 个整数 $k$($k<n$)。从 $n$ 个整数中任选 $k$ 个整数相加,可分别得到一系列的和。例如当 $n=4$,$k=3$,$4$ 个整数分别为 $3,7,12,19$ 时,可得全部的组合与它们的和为:\n\n$3+7+12=22$\n\n$3+7+19=29$\n\n$7+12+19=38$\n\n$3+12+19=34$\n\n现...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments