1.题目描述：点击打开链接
2.解题思路：本题利用双向查找解决。双向查找一般用于求若干个数之和相加等于一个固定值的题目。一般方法是将n个数分为两部分：1~n/2和n/2+1到n，然后枚举出两部分的所有可能的结果，最后利用二分查找看第一部分的结果是否存在于第二部分中。本题也是让找一些数之和等于S，这个数还可以变成对应的阶乘数，由于阶乘的个数受到k的限制。因此可以利用dfs来枚举所有的情况。由于最后要求出方案的个数，，因此一组sum，k（和值和已经使用的k的个数）和它出现的次数构成一个映射，因此用map来保存，即定义map<P,int>a，其中P就是pair<LL,int>类型。其他的过程就和双向搜索的主过程一样了。详细细节见代码注释。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 25typedef long long LL;typedef pair<LL, int> P;map<P, int>a, b;int val[N];LL f[N], S;int _n, _k;void dfs1(int pos, LL sum, int k){if (sum > S)return;if (k > _k)return;if (pos > _n / 2){a[P(sum, k)]++;return;}dfs1(pos + 1, sum + val[pos], k);dfs1(pos + 1, sum, k);if (val[pos] <= 20)dfs1(pos + 1, sum + f[val[pos]], k + 1);}void dfs2(int pos, LL sum, int k){if (sum > S)return;if (k > _k)return;if (pos > _n){b[P(sum, k)]++;return;}dfs2(pos + 1, sum + val[pos], k);dfs2(pos + 1, sum, k);if (val[pos] <= 20)dfs2(pos + 1, sum + f[val[pos]], k + 1);}int main(){//freopen("t.txt", "r", stdin);f[0] = f[1] = 1;for (int i = 2; i <= 20; i++)f[i] = f[i – 1] * i;//计算阶乘while (cin >> _n >> _k >> S){a.clear(), b.clear();for (int i = 1; i <= _n; i++)scanf("%d", val + i);dfs1(1, 0, 0);//先计算1到_n/2之间的所有情况，结果存放在a中dfs2(_n / 2 + 1, 0, 0);//再计算_n/2+1到_n的所有情况，结果存放在b中LL ans = 0;map<P, int>::iterator it = a.begin();for (it; it != a.end(); it++){int j = ((*it).first).second;//第一部分中使用了j个感叹号for (int i = 0; i + j <= _k; i++){if (b.count(make_pair(S – (it->first).first, i)))ans += (LL)it->second*b[make_pair(S – (it->first).first, i)];}}cout << ans << endl;}return 0;}
人要想成为生活的主人,不仅要适应生活,而且还要发挥主动性,
