Bx≠0\))问马跳到点\((Ex,Ey)\)且不经过任意障碍点的方案数。
我们假设一个点\((a,b)\)可以经过\(x\)次第一种跳法和\(y\)次第二种跳法跳到
则显然可以列出方程组:
同理,我们也可以求出\(y\)
如果我们以\((x,y)\)为每个点新的坐标,就把原先的问题转化成了一个很套路的坐标系上走路问题:
从\((0,0)\)出发每次只能向上或向右走一个单位,且不能经过任意障碍点求到达终点的方案数。
我们除去横纵坐标比终点大的障碍点然后把所有障碍点按坐标排序,最后把终点加到所囿障碍点之后成为第\(n\)个障碍点
设\(f_i\)为到达第\(i\)个障碍点且不经过之前任意障碍点的方案数,则答案就是\(f_n\)
现在,要考虑如何求\(f_i\)
既然要不经過之前任意障碍点,我们就求出经过之前若干障碍点的方案数然后用总方案数减去非法方案数就是合法方案数。
则如何求出非法方案數呢?
考虑既然经过了障碍点且障碍点又是有序的,我们可以枚举之前经过的第一个障碍点\(j\)
那么,在到达\(j\)之前不能经过任何障碍点;到达\(j\)与到达\(i\)之间,可以任意走
如果定义一个函数\(tot(p,q)\)表示从第\(p\)个障碍点到第\(q\)个障碍点的方案数,那么就有转移方程: