The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Contents:

Brute force
Meet-in-the-middle search + map or hash table
Meet-in-the-middle search + two pointers + a ~~different from DFS~~ strange state-enumeration method
1. First two-pointer method
2. Second two-pointer method
Complete code

The reading experience is better on the blog.

1. Problem Statement

You are given $n$ two-dimensional vectors. For every $k$ with $1\le k\le n$ , determine how many selection schemes choose exactly $k$ of the $n$ vectors such that their sum is $(x_g,y_g)$ .

2. Analysis

2.1 Brute-Force Algorithm

On seeing this problem, we can quickly think of a partial-score solution: brute-force every possible selection scheme, test whether the selected vectors sum to the target vector, and add every valid scheme to the answer. However, $n=40$ , and this algorithm has complexity $2^n$ , so it will certainly time out.

2.2 Meet-in-the-Middle Search + Map or Hash Table

2.2.1 Brief Idea

Meet-in-the-middle search in this problem means dividing the $n$ vectors into two parts. For each part, brute-force all possible selection schemes, then store those schemes and the result of each scheme—their vector sum—in some form. Finally, match schemes from the two parts and add those whose combined sum equals $(x_g,y_g)$ to the answer.

2.2.2 Details

To achieve the effect described above, we can use an STL map or unordered_map to store every selection scheme. A hand-written hash table also works, although it may take more time to implement. I recommend unordered_map, because map has $O(\log n)$ complexity and will be too slow for this problem, while the ideal complexity of unordered_map and a hand-written hash table is $O(1)$ . Of course, when using unordered_map, the hash function must be good enough to avoid being defeated by the tests—~~for example, my current version cannot pass~~.

The usual way to brute-force the states is DFS, which is also relatively easy to write. The two-pointer section of this solution introduces a rather strange method; readers interested in it can skip ahead.

Note: below, “map” refers collectively to unordered_map, map, or a hand-written hash table.

First create two maps, fir and sec, which store selection schemes for the first and second halves of the vectors, respectively. The key for each map can be a structure containing three integers, $(\text{sum}_x,\text{sum}_y,k)$ . Here, $(\text{sum}_x,\text{sum}_y)$ is the sum of all vectors selected by the current scheme, and $k$ is the number of vectors selected by that scheme. Many schemes may have exactly the same $x$ , $y$ , and $k$ , so the value in the map is the number of schemes sharing those three values.

To store the answer, create an array ans[n], where ans[i] denotes the number of selection schemes when $k=i$ .

After finding the schemes for both parts, we combine valid pairs and add them to the answer. Every scheme stored in a map contains its vector sum $(\text{sum}_x,\text{sum}_y)$ . Let the vector sum of a scheme from the first half be $\vec{v_1}$ and that of a scheme from the second half be $\vec{v_2}$ . If $\vec{v_1}+\vec{v_2}=(x_g,y_g)$ , record this combination in the answer.

Because we use maps, we do not need a genuine nested loop that traverses every pair of schemes. For a possible match, $\vec{v_1}+\vec{v_2}=(x_g,y_g)$ . We can use a double loop whose first level enumerates the fir map and whose second level enumerates the current $k$ . Inside the loop, write conceptually:

ans[current k] += it_fir.value * sec[{x_g - it_fir.key.x, y_g - it_fir.key.y, current k - it_fir.key.k}]

Here, it_fir is an iterator over fir. The scheme represented by sec[{x_g - it_fir.key.x, y_g - it_fir.key.y, current k - it_fir.key.k}] and the scheme currently visited by it_fir satisfy $\vec{v_1}+\vec{v_2}=(x_g,y_g)$ , while the total number of selected vectors in the two schemes equals the current $k$ . Since the values of the two maps are the numbers of schemes satisfying those conditions, multiply the two values to obtain the number of all valid pairings.

2.3 Meet-in-the-Middle Search + Two Pointers

The theoretical complexity of two pointers appears to be the same as that of a hash table, but a poor hash function can make a hash table much slower. Two pointers do not have this problem.

2.3.1 Two Pointers A

First create two vectors, fir and sec. Their element type is the same as the map key above: $(\text{sum}_x,\text{sum}_y,k)$ . fir stores schemes produced from the first half of the vectors, while sec stores those from the second half.

After enumerating every scheme, sort both vectors according to the following rule:

1
2
3

if(a.x != b.x) return x < b.x;
if(a.y != b.y) return y < b.y;
return a.k < b.k;

Then create two pointers. Initialize $p_1$ to 1 and $p_2$ to sec.size() - 1, the last element of sec. At this point, $p_1$ points to the smallest element in fir, and $p_2$ points to the largest element in sec.

Consider how to make the sum of the vectors $\vec{v_1}$ and $\vec{v_2}$ at the current pointers equal $(x_g,y_g)$ . If we need to increase $\vec{v_1}+\vec{v_2}$ , we can only increase $p_1$ , because $p_2$ already points to the largest element of its array. Conversely, if we need to decrease $\vec{v_1}+\vec{v_2}$ , we can only decrease $p_2$ . In code, this is:

int p1 = 0, p2 = sec_half.size() - 1;
while(p1 < fir_half.size() && p2 >= 0){
   Instruct &f = fir_half[p1], &s = sec_half[p2];
   if(f.x + s.x < tar_x ||(f.x + s.x == tar_x && f.y + s.y < tar_y)){
      // If the sum of the two vectors is below the target, only p1 can be increased,
      // because p2 initially points to the largest element.
      p1++;
   }
   else if(f.x + s.x > tar_x ||(f.x + s.x == tar_x && f.y + s.y > tar_y)){
      // If the sum of the two vectors is above the target, only p2 can be decreased,
      // because p1 initially points to the smallest element.
      p2--;
   }
   // The latter half of the code is inserted here.
}

Note: Instruct is a structure containing the three integers {x, y, k}.

This method guarantees that we eventually find cases where $\vec{v_1}+\vec{v_2}=(x_g,y_g)$ . However, both arrays may contain a consecutive run of completely identical values, meaning that multiple $p_1,p_2$ pairs satisfy the equation. We therefore need to find the exact boundaries of this valid consecutive run.

The preceding code has already found the smallest valid $p_1$ and the largest valid $p_2$ . To determine the full range, we also need the largest valid $p_1$ and the smallest valid $p_2$ . This is simple: every value in the consecutive run is identical, so we only need to compare each current element with the first element of the run.

We must also add valid pairings to answers grouped by $k$ . Create two arrays, fir_same_k and sec_same_k. fir_same_k[i] is the number of entries with $k=i$ in the valid run of the first array, and sec_same_k has the corresponding meaning for the second array.

This yields the following code. Insert it after the else if in the preceding snippet:

else{
   int p1t, p2t;
   
   memset(fir_same_k, 0, sizeof(fir_same_k));
   memset(sec_same_k, 0, sizeof(sec_same_k));
   
   // The valid runs found each time do not overlap, so clear the arrays each time.

   for(p1t = p1; p1t < fir_half.size() && fir_half[p1t] == f; p1t++){
      // p1t denotes the largest p1 satisfying v_1 + v_2 == (x_g, y_g).
      fir_same_k[fir_half[p1t].k]++;
   }
   for(p2t = p2; p2t >= 0 && sec_half[p2t] == s; p2t--){
      // p2t denotes the smallest p2 satisfying v_1 + v_2 == (x_g, y_g).
      sec_same_k[sec_half[p2t].k]++;
   }

   // Count answers by enumerating possible k values in both halves.
   for(int i = 0; i <= 20; i++){
      for(int j = 0; j <= 20; j++){// 20 can actually be replaced by n / 2 + 1.
         ans[i + j] += 1LL * fir_same_k[i] * sec_same_k[j];
         // Multiply because any scheme represented by the same fir_same_k[i] and
         // sec_same_k[j] is completely identical in x, y, and k.
      }
   }
   p1 = p1t, p2 = p2t;// Without this, the loop remains forever in the same run.
}

This method runs relatively quickly; see the submission record.

2.3.2 Two Pointers B

In method A, counting the answers requires the arrays fir_same_k and sec_same_k to group cases with the same $k$ . We can improve the method by grouping schemes with the same $k$ at the time states are enumerated.

More specifically, change the vectors fir and sec into vector<Instruct> fir[20], sec[20]. fir[i] stores all first-half schemes with $k=i$ , and sec[i] stores the second-half schemes with $k=i$ . Since the storage method changes, the later two-pointer stage must change as well.

This time, use a double loop to enumerate different fir[i] and sec[j] arrays. Inside the loop, perform work similar to method A. In other words, because the $k$ values of the current first-half and second-half schemes are already known, two pointers need only find the ranges of $p_1$ and $p_2$ satisfying $\vec{v_1}+\vec{v_2}=(x_g,y_g)$ .

for(int fir_k = 0; fir_k <= n / 2 + 1; fir_k++){   // Enumerate k for the first half.
   for(int sec_k = 0; sec_k <= n / 2 + 1; sec_k++){// Enumerate k for the second half.
      int p1 = 0, p2 = sec_half[sec_k].size() - 1;
      while(p1 < fir_half[fir_k].size() && p2 >= 0){
         Instruct &f = fir_half[fir_k][p1], &s = sec_half[sec_k][p2];
         if(f.x + s.x < tar_x ||(f.x + s.x == tar_x && f.y + s.y < tar_y)){
            p1++;
            // Find the smallest p1 satisfying v_1 + v_2 == (x_g, y_g) for this fir_k.
         }
         else if(f.x + s.x > tar_x ||(f.x + s.x == tar_x && f.y + s.y > tar_y)){
            p2--;
            // Find the largest p2 satisfying v_1 + v_2 == (x_g, y_g) for this sec_k.
         }
         else{
            int p1t = p1, p2t = p2;
            while(p1t < fir_half[fir_k].size() && fir_half[fir_k][p1t] == f){
               p1t++;
            }
            while(p2t >= 0 && sec_half[sec_k][p2t] == s){
               p2t--;
            }
            
            ans[fir_k + sec_k] += 1LL * (p1t - p1) * (p2 - p2t); 
            // Multiply the length of the p1 range by the length of the p2 range.
            // Detail: a range length would normally be p1t - p1 + 1. Observe the two
            // preceding while loops: after they terminate, p1t is one greater than the
            // correct p1t, and p2t is one less than the correct p2t. If either were still
            // correct, the loop would execute again. Thus no +1 is needed here.
            p1 = p1t, p2 = p2t;
         }
      }
   }
}

What advantage does method B have over method A? It saves space. With method A, the structure storing a scheme must contain the three integers $x,y,k$ . Note that $k$ is at most 20, yet an int or short must still be used to store it. Because 20 is so small, either data type wastes a large amount of space. With method B, the structure contains only the two integers $x,y$ ; $k$ is stored in the array index. As long as the array size equals the maximum $k$ , no space is wasted.

For a concrete comparison, see this submission record. Compared with method A, method B uses approximately 17 MB less memory.

There is a cost: method B is slightly slower. I estimate that this mainly comes from the two-pointer stage; the sorting stage is actually somewhat faster. In any case, both methods have the same theoretical complexity, because each selection scheme is visited at most once.

2.4 A Strange State-Enumeration Method

The common state-enumeration method for this problem is DFS. Here is a rather strange alternative. In a selection scheme, every vector has two states: selected or not selected. Because there are only these two states, a binary number can represent the complete state. Bit $i$ indicates whether vector $i$ is selected. For example, $(101)_2$ selects vectors 1 and 3 but not vector 2.

To enumerate every state, increment a number from 0 through $2^n$ and inspect whether each bit is 0 or 1 at every increment. Because we use meet-in-the-middle search here, the number only needs to reach $2^{\frac n2}$ .

In terms of complexity, this may even be slower than DFS, and it uses more code. Every increment still requires a loop that checks the number from its first bit through its twentieth bit. On the other hand, because it avoids recursion, it does not repeatedly allocate stack frames for recursive functions, so memory usage may be slightly lower.

I do not recommend writing this during a real contest, since DFS is genuinely convenient. This is included only as an entertaining alternative.

3. Complete Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
const int MAXN = 45;

struct Instruct{
    ll x, y;
    int k;
    const bool operator < (Instruct b) const{
        if(x != b.x) return x < b.x;
        if(y != b.y) return y < b.y;
        return k < b.k;
    }
    const bool operator == (Instruct b) const{
        return x == b.x && y == b.y;
    }
}ins[MAXN];

vector<Instruct> fir_half, sec_half;
ll ans[MAXN];
int mx_state;
int n;
int tar_x, tar_y;

void vec_sum(int st, int ed, int cur_state, vector<Instruct> *cur_half){
    // Accumulate selected vectors according to the supplied state cur_state.
    // The search is split into two parts, so st and ed identify the first and last
    // vectors participating in the current part of the search.
    ll tot_x = 0, tot_y = 0;
    int k = 0;
    int len = ed - st + 1;
    for(int i = 1; i <= len; i++){
        if(cur_state & (1 << (i - 1))){
            tot_x += ins[st + i - 1].x, tot_y += ins[st + i - 1].y;
            k++;
        }
    }
    (*cur_half).push_back({tot_x, tot_y, k});
}

void state_generator(bool mode){
    // mode indicates whether the first or second half is being processed: 0 for first, 1 for second.
    rg int cur_state = 0;// Initial state: select nothing.
    int st, ed;
    vector<Instruct> *cur_half;// fir_half and sec_half store schemes for the respective halves;
                               // cur_half indicates where the current search stores its schemes.
    if(mode){
        cur_half = &sec_half;
        st = n / 2 + 1, ed = n;
        if(n & 1) mx_state = mx_state * 2 + 1;
        // mx_state is the greatest number representing a state. It starts as 2^(n/2),
        // but if n is odd, the second half contains one more vector than the first,
        // so the original mx_state must be multiplied by 2 and incremented by 1.
    }
    else{
        cur_half = &fir_half;
        st = 1, ed = n / 2;
    }

    while(cur_state <= mx_state){
        vec_sum(st, ed, cur_state, cur_half);
        cur_state++;
    }
}

int main(){
    scanf("%d%d%d", &n, &tar_x, &tar_y);
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld",&ins[i].x, &ins[i].y); 
    }
    for(int i = 0; i < n / 2; i++){
        mx_state = mx_state | (1 << i);
        // The largest state consists of n/2 bits that are all 1.
    }
    state_generator(0); state_generator(1);
    
    sort(fir_half.begin(), fir_half.end());
    sort(sec_half.begin(), sec_half.end());

    rg int p1 = 0, p2 = sec_half.size() - 1;
    int fir_same_k[21], sec_same_k[21];

   while(p1 < fir_half.size() && p2 >= 0){
        Instruct &f = fir_half[p1], &s = sec_half[p2];
        if(f.x + s.x < tar_x ||(f.x + s.x == tar_x && f.y + s.y < tar_y)){
            // If the sum is below the target, only p1 can be increased because p2
            // initially points to the greatest element.
            p1++;
        }
        else if(f.x + s.x > tar_x ||(f.x + s.x == tar_x && f.y + s.y > tar_y)){
            // If the sum is above the target, only p2 can be decreased because p1
            // initially points to the smallest element.
            p2--;
        }
        else{
            int p1t, p2t;
            memset(fir_same_k, 0, sizeof(fir_same_k));
            memset(sec_same_k, 0, sizeof(sec_same_k));
            // Valid runs found in separate iterations do not overlap, so clear the arrays.
            for(p1t = p1; p1t < fir_half.size() && fir_half[p1t] == f; p1t++){
                // p1t is the largest p1 satisfying v_1 + v_2 == (x_g, y_g).
                fir_same_k[fir_half[p1t].k]++;
            }
            for(p2t = p2; p2t >= 0 && sec_half[p2t] == s; p2t--){
                // p2t is the smallest p2 satisfying v_1 + v_2 == (x_g, y_g).
                sec_same_k[sec_half[p2t].k]++;
            }
            // Count answers by enumerating possible k values for both halves.
            for(int i = 0; i <= 20; i++){
                for(int j = 0; j <= 20; j++){// 20 can be replaced by n / 2 + 1.
                    ans[i + j] += 1LL * fir_same_k[i] * sec_same_k[j];
                    // Multiply because any schemes represented by the same fir_same_k[i]
                    // and sec_same_k[j] are identical in x, y, and k.
                }
            }
            p1 = p1t, p2 = p2t;// Without this, the loop remains forever in the same run.
        }        
    }

    for(int i = 1; i <= n; i++){
        printf("%lld\n", ans[i]);
    }
    system("pause");
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
const int MAXN = 45;

struct Instruct{
    ll x, y;
    const bool operator < (Instruct b) const{
        if(x != b.x) return x < b.x;
        return y < b.y;
    }
    const bool operator == (Instruct b) const{
        return x == b.x && y == b.y;
    }
}ins[MAXN];
vector<Instruct> fir_half[MAXN], sec_half[MAXN];
ll ans[MAXN];
int mx_state;
int n;
int tar_x, tar_y;

void vec_sum(int st, int ed, int cur_state, vector<Instruct> *cur_half){
    // Accumulate selected vectors according to the supplied state cur_state.
    // The search is split into two parts, so st and ed identify the first and last
    // vectors participating in the current part of the search.
    ll tot_x = 0, tot_y = 0;
    int k = 0;
    int len = ed - st + 1;
    for(int i = 1; i <= len; i++){
        if(cur_state & (1 << (i - 1))){
            tot_x += ins[st + i - 1].x, tot_y += ins[st + i - 1].y;
            k++;
        }
    }
    cur_half[k].push_back({tot_x, tot_y});
}

void state_generator(bool mode){
    // mode indicates whether the first or second half is processed: 0 for first, 1 for second.
    rg int cur_state = 0;// Initial state: select nothing.
    int st, ed;
    vector<Instruct> *cur_half;
    if(mode){ 
        cur_half = sec_half;
        st = n / 2 + 1, ed = n;
        if(n & 1) mx_state = mx_state * 2 + 1;
        // mx_state is the largest number representing a state. It starts as 2^(n/2),
        // but when n is odd the second half contains one extra vector, so multiply the
        // original mx_state by 2 and add 1.
    }
    else{
        cur_half = fir_half;
        st = 1, ed = n / 2;
    }

    while(cur_state <= mx_state){
        vec_sum(st, ed, cur_state, cur_half);
        cur_state++;
    }
}

int main(){
    scanf("%d%d%d", &n, &tar_x, &tar_y);
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld",&ins[i].x, &ins[i].y); 
    }
    for(int i = 0; i < n / 2; i++){
        mx_state = mx_state | (1 << i);
        // The largest state consists of n/2 bits that are all 1.
    }
    state_generator(0); state_generator(1);
    
    for(int i = 0; i <= n / 2 + 1; i ++){
        sort(fir_half[i].begin(), fir_half[i].end());
        sort(sec_half[i].begin(), sec_half[i].end());
    }

    for(int fir_k = 0; fir_k <= n / 2 + 1; fir_k++){   // Enumerate k for the first half.
        for(int sec_k = 0; sec_k <= n / 2 + 1; sec_k++){// Enumerate k for the second half.
            int p1 = 0, p2 = sec_half[sec_k].size() - 1;
            while(p1 < fir_half[fir_k].size() && p2 >= 0){
                Instruct &f = fir_half[fir_k][p1], &s = sec_half[sec_k][p2];
                if(f.x + s.x < tar_x ||(f.x + s.x == tar_x && f.y + s.y < tar_y)){
                    p1++;
                    // Find the smallest p1 satisfying v_1 + v_2 == (x_g, y_g) for fir_k.
                }
                else if(f.x + s.x > tar_x ||(f.x + s.x == tar_x && f.y + s.y > tar_y)){
                    p2--;
                    // Find the largest p2 satisfying v_1 + v_2 == (x_g, y_g) for sec_k.
                }
                else{
                    int p1t = p1, p2t = p2;
                    while(p1t < fir_half[fir_k].size() && fir_half[fir_k][p1t] == f){
                    p1t++;
                    }
                    while(p2t >= 0 && sec_half[sec_k][p2t] == s){
                    p2t--;
                    }
                    
                    ans[fir_k + sec_k] += 1LL * (p1t - p1) * (p2 - p2t); 
                    // Multiply the p1 range length by the p2 range length.
                    // Detail: a range length would normally be p1t - p1 + 1, but after
                    // the two while loops p1t is one greater and p2t one smaller than the
                    // final valid values. If they were still valid, the loops would run
                    // once more. Thus no +1 is required when calculating the length.
                    p1 = p1t, p2 = p2t;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        printf("%lld\n", ans[i]);
    }
    system("pause");
}

I kept debugging this method, but even now it fails the time or memory limit. My hash function is probably broken, but I do not know the correct way to write it. If you want to use this approach, you can read solutions by other experts. If you know the method and can help me debug it, I would be very grateful. Here is the submission record, and I put the code here.