Codeforces Round #297(Div. 2) E. Anya and Cubes(양방향 DFS)

먼저 가장 폭력적인 방법을 생각해 보자. 우리는 DFS로 모든 가능한 해를 직접 검색한다. 그러면 각 층에 대해 세 가지 결정이 있다. 바로 이 수를 선택하지 않고 이 수를 선택하고 이 수의 계승을 선택하는 것이다.귀속 깊이가 최대 25, 시간 복잡도 O(3^25), 너무 커서 시간 복잡도를 낮출 방법을 강구해야 한다.이전 버전을 기억하십니까?우리는 네 개의 집합 중에서 매 집합마다 하나의 숫자를 선택하여 더하기를 한다. 하나의 수 S와 같냐고 묻는다. 우리의 방법은 두 집합 중의 모든 상황을 미리 처리한 다음에 2점을 나누는 것이다.이 문제도 같은 전략을 취할 수 있다. dfs를 두 번 진행하고 매번 깊이 n/2로 귀속시키면 복잡도를 O(3^13)*log(3^13)로 낮추는 데 성공한다.이것은 이론적인 경계이다. 사실 이 안에는 중복된 것이 많고 시간의 복잡도가 그렇게 높지 않다.
자세한 내용은 코드를 참조하십시오.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 35;
const int max_cnt = 2000000+5;
ll cal[maxn], a[maxn], n, k, S, ans;
void init() {
    cal[0] = 1;
    for(int i = 1; i <= 20; i++) {
        cal[i] = cal[i-1] * i;
    }
}
struct node {
    ll sum, k;
    node(ll ss=0, ll kk=0):sum(ss), k(kk) {}
    bool operator < (const node& rhs) const {
        return sum < rhs.sum || (sum == rhs.sum && k < rhs.k);
    }
}c[max_cnt],b[max_cnt];
map<node, int> p;
map<node, int> :: iterator it;
void dfs1(int d, ll sum, int _k) {
    if(_k > k) return ; // DFS，  n/2 
    if(d > n/2) {
        p[node(sum, _k)]++; return ;
    }
    dfs1(d+1, sum, _k);
    if(sum+a[d] <= S) dfs1(d+1, sum+a[d], _k);
    if(a[d] <= 20 && sum+cal[a[d]] <= S) dfs1(d+1, sum+cal[a[d]], _k+1);
}
void dfs2(int d, ll sum, int _k) {
    if(_k > k) return ; // DFS
    if(d > n) {
        it = p.lower_bound(node(S-sum,0)); // 
        for( ; it != p.end(); ++it) { // 
            if(it->first.sum == S-sum && _k+it->first.k <= k) ans += it->second;
            if(it->first.sum != S-sum) break;
        }
        return ;
    }
    dfs2(d+1, sum, _k);
    if(sum+a[d] <= S) dfs2(d+1, sum+a[d], _k);
    if(a[d] <= 20 && sum+cal[a[d]] <= S) dfs2(d+1, sum+cal[a[d]], _k+1);
}
int main() {
    init();
    while(~scanf("%I64d%I64d%I64d",&n,&k,&S)) {
        for(int i=1;i<=n;i++) {
            scanf("%I64d",&a[i]);
        }
        p.clear();
        ans = 0;
        dfs1(1,0,0);
        dfs2(n/2+1,0,0);
        printf("%I64d
",ans);
    }
    return 0;
}