CF525E Anya and Cubes

发表于 更新于 分类于 阅读次数：

CF525E Anya and Cubes 人生第一道紫题（某愚人节题目不算 题目大意为每个数a，可以sum+=a,sum+=a!,sum+=0，求有几种sum==S的方案 本题用到了一种叫做meet in the middle的搜索方法，即把从0n的搜索改为0n/2，n/2+1n的搜索，搜完之后合并答案以减少时间复杂度 可以看出，合并部分的速度决定了最终算法的时间复杂度，如何合并是本题的关键，我使用了stl::map解决此问题 将枚举a[0]!-a[n]!改为分别枚举a[0]-a[n/2]!与a[n/2+1]a[n]，用map储存前半部分的结果。ans[k][sum]表示当使用k个!时和为sum的方案总数 在枚举后半部分时，找到sum时，加上所有方案数：ans[i][S-sum]，0<=i<=K-k即可

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;
}