给定一个\(h \times w\) 大小的棋盘，其中有 \(n\) 个点为黑色。
每次只能向右或向下移动，求从 \((1,1)\) 不经过黑色点到达 \((h, w)\) 的方案数。
\(f(i)\) 表示到达第 \(i\) 个黑点的方案数，且在这之前都没有经过黑点。
考虑补集。求有多少种方案经过了至少一个黑点。
枚举第一个黑点 \(j\)。需要满足 \(x_j \le x_i,y_j \le y_i\)。那么：
\[f(i) = \dbinom{x_i+y_i-2}{x_i-1} - \sum_{x_j \le x_i, y_j \le y_i}f(j) \times \dbinom {x_i-x_j+y_i-y_j}{x_i-x_j} \]强行加入第 \(n + 1\) 个黑点 \((h, w)\)。那么答案为 \(f(n+1)\)。
事实上转移顺序不太好定。所以记忆化搜索！
https://codeforces.com/contest/559/submission/291158046
标签：Giant,le,黑点,Gerald,times,Chess From： https://www.cnblogs.com/2huk/p/18542187