题解

CF Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) E

因为经过$\log(s)$个点后$s$就一直是$1$了，因此我们只需要记经过前$\log(s)$个点的信息，后面的归到一类即可。
设$f(i,j)$表示到第$i$个点经过了$j$个点的方案数，设$P(i,j)$为第$i$个点到第$j$个点的路径数（不管经没经过点），那么：

$$P(i,j) = \binom{x _ j - x _ i + y _ j - y _ i}{x _ j - x _ i}$$
因为$f(i,j)=所有方案-\sum _ {k < j} f(i, k) - 大于j的方案$，因为所有大于$j$的方案之前都必定经过了一个点作为第$j$个点，因此枚举经过的第$j$个点是哪个即可，所以转移方程是：
$$f(i,j) = P(0,i) - \sum _ {k < j} f(i,k) - \sum _ {k < i}P(k,i)f(k,j)$$
注意当$j>\log(s)$时，就不需要减去大于的方案数了，因为大于$\log(s)$的都归类到$\log(s) + 1$上去了。
时间复杂度$O(n ^ 2\log(s))$。