P4799 [CEOI2015 Day2]世界冰球锦标赛

题意：

01背包求方案数，体积上限为 \(m\)

\(n\le 40,1\le a_i\le 1e16,1\le m\le 1e18\)

思路：

折半搜索板子题。

v1表示只考虑左半数组，能凑出来的所有体积的集合。v2同理。

合并答案应该也可以双指针，但感觉排序也要带个log所以没必要。直接二分好了

const signed N = 43;
ll n, m, a[N];
vector v1, v2;

void dfs(int l, int r, ll sum, vector &ve) {
    if(sum > m) return;
    if(l > r) { ve.pb(sum); return; }
    dfs(l + 1, r, sum, ve);
    dfs(l + 1, r, sum + a[l], ve);
}

signed main() {
    iofast;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    dfs(1, n/2, 0, v1), dfs(n/2+1, n, 0, v2);
    sort(all(v2));

    ll ans = 0;
    for(ll s1 : v1)
        ans += upper_bound(all(v2), m-s1) - v2.begin();
    cout << ans;
}