canthangbang.cpp

#include<iostream>
#include<cstdlib>
#include<vector>
#include<unordered_map>
#include<algorithm>

#define long long long
#define nln '\n'

using namespace std;

void build_sum(
    const vector<long> &a,
    long bgn, long end,
    long sum,
    vector<long> &vsm,
    unordered_map<long, long> &cnt)
{
    if (bgn == end)
    {
        if (!cnt[sum])
            cnt[sum] = 1, vsm.push_back(sum);
        else
            ++cnt[sum];
        return;
    }
    build_sum(a, bgn+1, end, sum+a[bgn], vsm, cnt);
    build_sum(a, bgn+1, end, sum-a[bgn], vsm, cnt);
    build_sum(a, bgn+1, end, sum, vsm, cnt);
}

int main()
{
    // Input
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    //freopen("canthangbang.inp", "r", stdin);
    long n, m;
    cin >> n >> m;
    vector<long> a(n);
    for (auto &i : a)
        cin >> i;
    // Process
    vector<long> sm1, sm2;
    unordered_map<long, long> co1, co2;
    build_sum(a, 0, n/2, 0, sm1, co1);
    build_sum(a, n/2, n, 0, sm2, co2);
    sort(sm2.begin(), sm2.end());
    long ans = 0;
    for (auto i : sm1)
        if (binary_search(sm2.begin(), sm2.end(), m-i))
            ans += co1[i]*co2[m-i];
    cout << ans << nln;
    return 0;
}