Atcoder ARC058D Iroha and a Grid
考虑从第 \(b\) 列与第 \(b + 1\) 之间分开这个矩阵，钦定 \((i, b)\) 下一步必须走到 \((i, b + 1)\)，可以发现这样是不会漏算或算重的。
于是就可以用乘法原理算出这个 \(i\) 的贡献：\(\binom{(i - 1) + (b - 1)}{i - 1}\times \binom{(n - i) + (m - b - 1)}{n - i}\)，左半部分的就是 \((1, 1)\) 走到 \((i, b)\) 的方案数，右半部分就是 \((i, b + 1)\) 走到 \((n, m)\) 的方案数。
再用加法原理统计总答案：\(\sum\limits_{i = 1}^{n - a}\binom{(i - 1) + (b - 1)}{i - 1}\times \binom{(n - i) + (m - b - 1)}{n - i}\)。
时间复杂度 \(O(n + m)\)。