P8187 [USACO22FEB] Robot Instructions S

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

无

无

【样例解释】 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.