题目描述

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$.

题目大意

题目描述

贝西正在学习如何控制她最近作为礼物收到的机器人。

机器人初始在坐标平面上的点 $(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)$

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.