A1808 [USACO22FEB] Robot Instructions S

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// [USACO22FEB] Robot Instructions S
//
// 对每个 K，统计「从 N 条指令里选 K 条、位移和恰好是 (xg, yg)」的方案数。
//
// N <= 40，直接枚举 2^40 个子集太慢，所以用**折半搜索（meet in the middle）**：
//   1. 把 N 条指令分成两半，分别枚举各自的所有子集，记录「位移和 + 用了几条」；
//      每半最多 2^20 = 1M 个子集。
//   2. 左半选了 (x,y)、用了 k1 条，右半就要凑出 (xg-x, yg-y)、用了 K-k1 条。
//      所以只要把两半的子集和分别排序，再配对即可。
//   3. 配对时把左半的位移改成「目标的补」(xg-x, yg-y)，两边的键就完全一致，
//      可以用双指针一趟扫过去。

struct Sub {
    ll x, y;
    int k;
};

// 枚举 ins[l..r) 的所有子集
void gen(const vector<pair<ll, ll>>& ins, int l, int r, ll x, ll y, int k, vector<Sub>& out) {
    if (l == r) {
        out.push_back({x, y, k});
        return;
    }
    gen(ins, l + 1, r, x, y, k, out);                                      // 不选第 l 条
    gen(ins, l + 1, r, x + ins[l].first, y + ins[l].second, k + 1, out);  // 选第 l 条
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    ll xg, yg;
    cin >> xg >> yg;
    vector<pair<ll, ll>> ins(N);
    for (int i = 0; i < N; i++) cin >> ins[i].first >> ins[i].second;

    int mid = N / 2;
    vector<Sub> L, R;
    L.reserve(1ULL << mid);
    R.reserve(1ULL << (N - mid));
    gen(ins, 0, mid, 0, 0, 0, L);
    gen(ins, mid, N, 0, 0, 0, R);

    // 左半的位移取「目标的补」，这样两半就可以直接按位移配对
    for (auto& s : L) {
        s.x = xg - s.x;
        s.y = yg - s.y;
    }

    auto cmp = [](const Sub& a, const Sub& b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.y != b.y) return a.y < b.y;
        return a.k < b.k;
    };
    sort(L.begin(), L.end(), cmp);
    sort(R.begin(), R.end(), cmp);

    vector<ll> ans(N + 1, 0);

    size_t i = 0, p = 0;
    while (i < L.size()) {
        // 找出左半里位移和相同的一组 [i, j)
        size_t j = i;
        while (j < L.size() && L[j].x == L[i].x && L[j].y == L[i].y) j++;

        // 右半里同样位移和的一组 [p, q)
        while (p < R.size() && (R[p].x < L[i].x || (R[p].x == L[i].x && R[p].y < L[i].y))) p++;
        if (p < R.size() && R[p].x == L[i].x && R[p].y == L[i].y) {
            size_t q = p;
            while (q < R.size() && R[q].x == R[p].x && R[q].y == R[p].y) q++;

            // 同一组里按「用了几条」汇总，再做一次卷积
            vector<pair<int, ll>> lv, rv;
            for (size_t t = i; t < j;) {
                size_t t2 = t;
                while (t2 < j && L[t2].k == L[t].k) t2++;
                lv.push_back({L[t].k, (ll)(t2 - t)});
                t = t2;
            }
            for (size_t t = p; t < q;) {
                size_t t2 = t;
                while (t2 < q && R[t2].k == R[t].k) t2++;
                rv.push_back({R[t].k, (ll)(t2 - t)});
                t = t2;
            }
            for (auto& a : lv) {
                for (auto& b : rv) {
                    ans[a.first + b.first] += a.second * b.second;
                }
            }
            p = q;
        }
        i = j;
    }

    for (int k = 1; k <= N; k++) cout << ans[k] << "\n";
    return 0;
}