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
| #include <bits/stdc++.h> #define ll long long using namespace std;
inline ll read() { ll a = 0; char c; do { c = getchar(); } while (c>'9' c<'0'); do { a = a * 10 + c - '0'; c = getchar(); } while (c >= '0'&&c <= '9'); return a; }
ll N, K, S; ll jc[21] = { 1,1,2,6,24,120,720,5040,40320,362880, 3628800,39916800,479001600,6227020800, 87178291200,1307674368000,20922789888000, 355687428096000,6402373705728000,121645100408832000, 2432902008176640000 }; ll a[30]; map<ll, ll> ans[30]; ll tot;
void dfs1(ll n, ll k, ll sum) { if (sum>S sum<0 k == K + 1) return; if (n == N / 2) { ++ans[k][sum]; return; } dfs1(n + 1, k, sum); dfs1(n + 1, k, sum + a[n]); if (a[n] <= 20) dfs1(n + 1, k + 1, sum + jc[a[n]]); }
void dfs2(ll n, ll k, ll sum) { if (sum>S sum<0 k == K + 1) return; if (n == N) { for (int i = 0; i <= K - k; ++i) if (ans[i].find(S - sum) != ans[i].end()) tot += ans[i][S - sum]; return; } dfs2(n + 1, k, sum); dfs2(n + 1, k, sum + a[n]); if (a[n] <= 20) dfs2(n + 1, k + 1, sum + jc[a[n]]); }
int main() { N = read(); K = read(); S = read(); for (int i = 0; i<N; ++i) a[i] = read(); dfs1(0, 0, 0); dfs2(N / 2, 0, 0); cout << tot; return 0; }
|