题解 CF525E 【Anya and Cubes】

首先我们一眼就能看出来这道题的思路是$\text{meet\ in\ the\ middle}$~~`好吧其实是因为yanQval直接提供了思路`~~。 注意到对于每个数都有三种状态：不选，选，选且阶乘，故直接$\text{dfs}$的复杂度为$3^n$，而采用$\text{meet\ in\ the\ middle}$的话是$\displaystyle{2\times 3^{\frac{n}{2}}}$，刚好能卡进时间范围内。 首先我们介绍一个$\text{C++11STL}$神器就是$\text{unordered\_map}$，写法与$\text{map}$完全一样，但是这个东西比$\text{map}$快的不止一点，$\text{map}$的查询复杂度是$\text{O(log n)}$的，但这个的查询复杂度是常数时间。当然神奇的$\text{\_\_gnu\_pbds}$里面的$\text{gp\_hash\_table}$跟这个差不多快~~`反正NOIP考试都tm不给用`~~ 然后就是常规操作了…… 首先预处理阶乘数组。 ``` fact[1] = 1ll; for (int i = 2; i <= 20; i ++) fact[i] = fact[i - 1] * i; ``` 对于前一半，每一个状态我们记录下两个值，一个是目前用了几个阶乘符号，一个是目前的和，即$\text{unordered\_map<long long, long long>M[MAXN]}$，其中$\text{M[k][i]}$表示前一半的数使用了$\text{k}$个阶乘符号，得到的和为$\text{i}$的方案数。 ``` unordered_map<long long, long long>M[MAXN]; void dfs1(int now, int end, long long S, int used) { if (used > k) return ; if (now > end) { M[used][S] ++; return ; } dfs1(now + 1, end, S, used); dfs1(now + 1, end, S + a[now], used); if (a[now] <= 20) dfs1(now + 1, end, S + fact[a[now]], used + 1); } // 下面是调用语句 dfs1(1, n / 2, 0, 0); ``` 对于后一半，我们采用与前一半相同的递归方式，不同的是对于每个状态，我们只需要判断前一半所得到的所有状态中，有没有能与之对应并组成答案的，最后再加上可行方案数即可。 ### 这里要特别说一句，不一定要用到$\text k$个阶乘符号，小于等于$\text k$就可以了。 ``` void dfs2(int now, int end, long long S, int used) { if (used > k) return ; if (S > s) return ; if (now > end) { for (int i = 0; i <= k - used; i ++) ans += M[i][s - S]; return ; } dfs2(now + 1, end, S, used); dfs2(now + 1, end, S + a[now], used); if (a[now] <= 20) dfs2(now + 1, end, S + fact[a[now]], used + 1); } ``` 由于我们用了更强大的数据结构，所以不需要任何优化。（我不是针对$\text{Pascal}$党，但是$\text{STL}$真的可以为所欲为） 贴一发完整代码： ``` #include <bits/stdc++.h> using namespace std; const int N = 30; unordered_map<long long, long long>M[N]; long long fact[N]; int n, k, a[N]; long long s, ans; void dfs1(int now, int end, long long S, int used) { if (used > k) return ; if (now > end) { M[used][S] ++; return ; } dfs1(now + 1, end, S, used); dfs1(now + 1, end, S + a[now], used); if (a[now] <= 20) dfs1(now + 1, end, S + fact[a[now]], used + 1); } void dfs2(int now, int end, long long S, int used) { if (used > k) return ; if (S > s) return ; if (now > end) { for (int i = 0; i <= k - used; i ++) ans += M[i][s - S]; return ; } dfs2(now + 1, end, S, used); dfs2(now + 1, end, S + a[now], used); if (a[now] <= 20) dfs2(now + 1, end, S + fact[a[now]], used + 1); } int main() { freopen("CF525E.in", "r", stdin); freopen("CF525E.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k >> s; fact[1] = 1ll; for (int i = 2; i <= 20; i ++) fact[i] = fact[i - 1] * i; for (int i = 1; i <= n; i ++) cin >> a[i]; dfs1(1, (n + 1) / 2, 0, 0); dfs2((n + 1) / 2 + 1, n, 0, 0); cout << ans << endl; return 0; } ```