You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
const int N = 30 ;
const int INF = 0x3f3f3f3f ;
int a [ N ] ;
bool st [ N ] ;
int n , k ;
int cnt ;
vector < int > path ;
bool isPrime ( int n ) {
if ( n < 2 ) return false ;
for ( int i = 2 ; i < = n / i ; i + + )
if ( n % i = = 0 ) return false ;
return true ;
}
/**
* 功能:遍历每个箱子,向箱子里装卡片
* @param step 走在第几个箱子面前
* @param sum 已经获得的数字和
* @return 获取可行方法数
*/
void dfs ( int step , int sum ) {
//当走到第k+1个虚拟箱子面前，
if ( step = = k + 1 ) {
if ( isPrime ( sum ) ) cnt + + ;
return ;
}
//在没有走完箱子时，考虑当前箱子放哪张卡片
for ( int i = path . size ( ) = = 0 ? 1 : path [ path . size ( ) - 1 ] + 1 ; i < = n ; i + + ) {
if ( ! st [ i ] ) {
st [ i ] = true ;
path . push_back ( i ) ;
dfs ( step + 1 , sum + a [ i ] ) ;
path . pop_back ( ) ;
st [ i ] = false ;
}
}
}
/*
4 3
3 7 12 19
答案：
*/
int main ( ) {
cin > > n > > k ;
for ( int i = 1 ; i < = n ; i + + ) cin > > a [ i ] ;
dfs ( 1 , 0 ) ;
cout < < cnt < < endl ;
return 0 ;
}
