Codeforces Round #297 (Div. 2) E.Anya and Cubes

なんとなく初めて解く部類の問題な気がする。

問題:http://codeforces.ru/problemset/problem/525/E

解法:数列a[]のn個のうちの最初のn/2個を全探索して取りうる値及びその値を取る場合の数を調べる。次にn/2個からn個にある数を全探索して同じことをする。以上の情報から条件に合う場合の数を求める。
以下ソースコード

ll fact[20];

void init() {
    fact[0] = 1;
    for (int i = 1; i < 20; i++) fact[i] = fact[i-1] * i;
}

const int MAXN = 30;
const ll MAX = 1e16;
ll a[MAXN];
map<ll, ll> lcnt[MAXN], rcnt[MAXN];
int n, k;
ll S;

void ldfs(int cur, int nn, int kk, ll sum) {
    if (cur == nn) {
        if (sum <= MAX) lcnt[kk][sum]++;
        return;
    }
    if (kk > k || sum > S) return;
    ldfs(cur+1, nn, kk, sum);
    ldfs(cur+1, nn, kk, sum+a[cur]);
    if (a[cur] < 19) ldfs(cur+1, nn, kk+1, sum+fact[a[cur]]);
}
void rdfs(int cur, int nn, int kk, ll sum) {
    if (cur == nn) {
        if (sum <= MAX) rcnt[kk][sum]++;
        return;
    }
    if (kk > k || sum > S) return;
    rdfs(cur+1, nn, kk, sum);
    rdfs(cur+1, nn, kk, sum+a[cur]);
    if (a[cur] < 19) rdfs(cur+1, nn, kk+1, sum+fact[a[cur]]);
}

int main() {
    init();
    cin >> n >> k >> S;
    for (int i = 0; i < n; i++) cin >> a[i];
    int nn = n/2;
    ldfs(0, nn, 0, 0);
    rdfs(nn, n, 0, 0);
    ll ans = 0;
    for (int kk = 0; kk <= k; kk++) {
        for (auto el : lcnt[kk]) {
            ll lsum = el.first;
            for (int kkk = 0; kkk <= k-kk; kkk++) {
                if (rcnt[kkk].find(S-lsum) != rcnt[kkk].end()) {
                    ans += rcnt[kkk][S-lsum] * lcnt[kk][lsum];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}