【BZOJ4767】两双手

首先可以发现,如果要在\(x\)方向上移动\(E_x\)步并且\(y\)方向上移动\(E_y\)步,设第一种走法用了\(a\)次,第二种走法用了\(b\)次,那么有

$$aA_x+bB_x=E_x$$
$$aA_y+bB_y=E_y$$

由于题目保证了\(\frac{A_x}{A_y}\neq \frac{B_x}{B_y}\),那么\(a\)和\(b\)可以直接解出。

问题就很简单了。把每个位置的\(a\)和\(b\)解出,就变成了一张网格图。问题变成每次向上或者向右走,到达一张有障碍的网格图的终点的方案数。

令\(f_i\)表示不经过障碍到达第\(i\)个关键点(障碍或终点)的方案数。那么显然可以将关键点排序后容斥计算。

说点什么

您将是第一位评论人!

提醒
wpDiscuz