CF 559 C - Gerald and Giant Chess
一道数学+DP 的 \(\color{#3498DB}\texttt{提高+/省选-}\) 题。
题目要求
求从 \((1,1)\) 点到 \((h,w)\) 点不经过黑色方格的路径数。
解题思路
观察数据范围，可以发现数据范围大概率与 \(n\) 有关。
首先，不考虑黑色方格，易发现路径数为 \(\mathrm{C}_{x+y-2}^{x-1}\)。
接下来考虑 DP，设 \(f_i\) 为从 \((1,1)\) 点到第 \(i\) 个黑色方格的路径数。根据减法原理，\((1,1)\) 点到第 \(i\) 个黑色方格的路径数为：\(\text{总路径数}-\text{经过的黑色方格的数量}\)。根据乘法原理，第 \(j\) 个黑色方格阻碍 \((1,1)\) 点到第 \(i\) 个方格的路径数为：\(f_j\times \mathrm{C}_{x_i+y_i-x_j-y_j}^{x_i-x_j}\ (x_i\ge x_j,y_i\ge y_j)\)。
所以，得到的状态转移方程为：
\[f_i=\mathrm{C}_{x+y-2}^{x-1}-\sum_{j=1}^{i-1}f_j\times \mathrm{C}_{x_i+y_i-x_j-y_j}^{x_i-x_j}\ (x_i\ge x_j,y_i\ge y_j) \]据此编写代码即可。
标签：总结,黑色,题目,数为,路径,ge,方格,mathrm From： https://www.cnblogs.com/TigerTanWQY/p/18030592