CVBB ACM Team

给定一个 $n\times m$ 的网格和初始点 $(a,b)$，求从初始点出发移动 $t$ 步且始终不出界的情况下的所有走法。

显然横轴坐标是独立的，可以分开考虑。

设 $f(s,n,a)$ 表示从一维坐标轴从 $a$ 点出发走 $s$ 步且始终处于 $[1,n]$ 范围内的情况下的所有走法。于是答案为

$$ \sum_{i=0}^t {t\choose i}f(i,n,a)f(t-i,m,b) $$

接下来考虑如何计算 $f(s,n,a)(s\in [0,t])$，$f(s,m,b)$ 的计算方式类同。

方案一：设 $\text{dp}(i,j)$ 表示走 $i$ 步最后位于 $j$ 点且始终为出界的方案数，不难得到一个 $O(nt)$ 的暴力解法。

方案二：不难发现，有

$$ \begin{equation}\begin{split} f(s,n,a)&=\sum_{i=1}^n \text{dp}(s,i) \\ &=\text{dp}(s-1,1)+\sum_{i=2}^{n-1} (\text{dp}(s-1,i-1)+\text{dp}(s-1,i+1))+\text{dp}(s-1,n)\\ & =2f(s-1,n,a)-\text{dp}(s-1,1)-\text{dp}(s-1,n) \end{split}\end{equation} $$

于是问题转化为计算 $\text{dp}(s,1),\text{dp}(s,n)$。