_yxl_gl_的博客

_yxl_gl_的博客

题解 CF525E 【Anya and Cubes】

posted on 2018-10-11 23:29:12 | under 题解 |

首先我们一眼就能看出来这道题的思路是 $\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;
}