1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include <bits/stdc++.h> #include <hash_map> #define MAXN 30 #define int long long using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=(x*10)+(ch-'0'); ch=getchar(); } return x*f; } int a[MAXN],fac[MAXN],n,k,S; unordered_map<int,int>Map[MAXN]; inline void Init(){ fac[1]=1; for (register int i=2;i<=20;++i){ fac[i]=fac[i-1]*i; } }
void dfs1(int l,int r,int Sum,int usek){ if (l>r){ Map[usek][Sum]++; return ; } dfs1(l+1,r,Sum,usek); dfs1(l+1,r,Sum+a[l],usek); if (a[l]<=20) dfs1(l+1,r,Sum+fac[a[l]],usek+1); } int ans; void dfs2(int l,int r,int Sum,int usek){ if (l>r){ for (register int i=0;i<=k-usek;++i){ ans+=Map[i][S-Sum]; } return ; } dfs2(l+1,r,Sum,usek); dfs2(l+1,r,Sum+a[l],usek); if (a[l]<=20) dfs2(l+1,r,Sum+fac[a[l]],usek+1); } #undef int int main(){ #define int long long Init(); n=read(),k=read(),S=read(); for (register int i=1;i<=n;++i){ a[i]=read(); } dfs1(1,n/2,0,0); dfs2(n/2+1,n,0,0); printf("%lld\n",ans); }
|