P8187 [USACO22FEB] Robot Instructions S

Bessie 正在学习如何控制她最近收到的一个机器人。机器人从坐标平面上的点 $(0,0)$ 开始，Bessie 希望机器人最终停在点 $(x_g,y_g)$。Bessie 最初有一个包含 $N$ 条指令的列表（$1 \le N \le 40$），第 $i$ 条指令会将机器人向右移动 $x_i$ 个单位，向上移动 $y_i$ 个单位（当 $x_i$ 和 $y_i$ 为负数时，分别向左和向下移动）。对于每一个从 $1$ 到 $N$ 的 $K$，帮助 Bessie 计算她可以从原始 $N$ 条指令中选择 $K$ 条指令的方式数，使得在执行完这 $K$ 条指令后，机器人将停在点 $(x_g,y_g)$。注意：本题的时间和内存限制为 4 秒和 512MB，是默认值的两倍。

第一行包含 $N$。下一行包含 $x_g$ 和 $y_g$，范围为 $-10^9 \cdots 10^9$。接下来的 $N$ 行描述了指令。每行有两个整数 $x_i$ 和 $y_i$，范围也为 $-10^9 \cdots 10^9$。保证 $(x_g,y_g) eq (0,0)$ 且对所有 $i$，$(x_i,y_i) eq (0,0)$。

输出 $N$ 行，对于每个从 $1$ 到 $N$ 的 $K$，Bessie 可以从原始 $N$ 条指令中选择 $K$ 条指令的方式数。

【样例解释】在这个例子中，有六种方式 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) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10) ``` 【数据范围】 - 测试用例 2-4 满足 $N \le 20$。 - 测试用例 5-16 不满足额外的约束条件。 题面翻译由 ChatGPT-4o 提供。