[USACO22FEB] Robot Instructions S

## 题目描述 贝西正在学习如何控制她最近作为礼物收到的机器人。 机器人初始在坐标平面上的点 $(0,0)$，Bessie 希望机器人在点 $(x_g,y_g)$ 停止。 Bessie 最初有一个包含 $N(1\leq N \leq 40)$ 条指令的指令列表给机器人，其中第 $i$ 个指令将向右移动机器人 $x_i$ 单位和向上移动 $y_i$ 单位（或者当 $x_i$ 和 $y_i$ 为负数时分别向左或向下移动）。 对于从 $1$ 到 $N$ 的每个 $K$，帮助 Bessie 计算她可以从原始 $N$ 中选择 $K$ 条指令的方案数，使得在执行 $K$ 条指令后，机器人将在点 $(x_g,y_g)$ 处停止。 ## 输入格式 第一行包含 $N$ 。下一行包含 $x_g$ 和 $y_g$，每个数都在 $-10^9\dots 10^9$ 的范围内。最后的 $N$ 行描述了指令。每行有两个整数 $x_i$ 和 $y_i$，也在 $-10^9\dots 10^9$ 范围内。 保证 $(x_g,y_g)\neq (0,0)$ 和对于所有的 $i，(x_i,y_i)\neq (0,0)$。 ## 数据范围 数据 $2\sim 4$ 满足 $N\leq 20$。 数据 $5\sim 16$ 无额外约束。 ### 样例解释 在此示例中，Bessie 可以通过六种方式选择指令： ``` (-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7) (-2,0) (3,0) (4,0) (0,10) (1 2 3 5) (-2,0) (3,0) (4,0) (0,10) (1 2 3 7) (5,0) (0,10) (0,-10) (0,10) (4 5 6 7) (5,0) (0,10) (4 5) (5,0) (0,10) (4 7) ``` 对于第一种方式，机器人的路径如下所示： $(0,0) \to (-2,0) \to (1,0) \to (5,0) \to (5,10) \to (5,0) \to (5,10)$

Bessie is learning how to control a robot she has recently received as a gift. The robot begins at point $(0,0)$ on the coordinate plane and Bessie wants the robot to end at point $(x_g,y_g)$. Bessie initially has a list of $N$ $(1\le N\le 40)$ instructions to give to the robot, the $i$-th of which will move the robot $x_i$ units right and $y_i$ units up (or left or down when $x_i$ and $y_i$ are negative, respectively). For each $K$ from $1$ to $N$, help Bessie count the number of ways she can select $K$ instructions from the original $N$ such that after the $K$ instructions are executed, the robot will end at point $(x_g,y_g)$. **Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

The first line contains $N$. The next line contains $x_g$ and $y_g$, each in the range $−10^9\cdots 10^9$. The final $N$ lines describe the instructions. Each line has two integers $x_i$ and $y_i$, also in the range $−10^9\cdots 10^9$. It is guaranteed that $(x_g,y_g)\neq (0,0)$ and $(x_i,y_i)\neq (0,0)$ for all $i$.

Print $N$ lines, the number of ways Bessie can select $K$ instructions from the original $N$ for each $K$ from $1$ to $N$.

7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10

0
2
0
3
0
1
0

【样例解释】 In this example, there are six ways Bessie can select the instructions: ``` (-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7) (-2,0) (3,0) (4,0) (0,10) (1 2 3 5) (-2,0) (3,0) (4,0) (0,10) (1 2 3 7) (5,0) (0,10) (0,-10) (0,10) (4 5 6 7) (5,0) (0,10) (4 5) (5,0) (0,10) (4 7) ``` For the first way, the robot's path looks as follows: ``` (0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10) ``` 【数据范围】 - Test cases 2-4 satisfy $N\le 20$. - Test cases 5-16 satisfy no additional constraints.