LeAf146's blog

1
#include<bits/stdc++.h>
2
#define endl "\n"
3
#define int long long
4
using namespace std;
5
int ppp[20];
6
void init(){
7
    int i=1;
8
    ppp[0]=1;
9
    for(;i<20;i++){
10
        ppp[i]=ppp[i-1]*i;
11
    }
12
}
13
int n,k,s,ans;
14
vector<int> v;
15
vector<unordered_map<int,int>> m;
16
void dfs1(int now,int end,int S,int used){
17
    if(used>k)return;
18
    if(S>s)return;
19
    if(now>end){
20
        m[used][S]++;
21
        return;
22
    }
23
    dfs1(now+1,end,S,used);
24
    dfs1(now+1,end,S+v[now],used);
25
    if(v[now]<=18)dfs1(now+1,end,S+ppp[v[now]],used+1);
26
}
27
void dfs2(int now,int end,int S,int used){
28
    if(used>k)return;
29
    if(S>s)return;
30
    if(now>end){
31
        for(int i=0;i<=k-used;i++)
32
            ans+=m[i][s-S];
33
        return;
34
    }
35
    dfs2(now+1,end,S,used);
36
    dfs2(now+1,end,S+v[now],used);
37
    if(v[now]<=18)dfs2(now+1,end,S+ppp[v[now]],used+1);
38
}
39
signed main(){
40
    std::ios::sync_with_stdio(false);std::cin.tie(0);
41
    init();
42
    ppp[0]=0;
43
    cin>>n>>k>>s;
44
    m.resize(n+1);
45
    v.resize(n);for(int i=0;i<n;i++)cin>>v[i];
46
    sort(v.begin(),v.end());
47
    dfs1(0,n/2,0,0);
48
    dfs2(n/2+1,n-1,0,0);
49
    cout<<ans<<endl;
50
    return 0;
51
}