简单组合计数。
可以先把矩形旋转一下，变为求从 \((1,1)\) 走到 \((n,m)\)，只能向上或向右移动。且不经过左上角的 \(A\times B\) 的禁区的方案数，对 \(10^9 + 7\) 取模。
假如没有 \(A\times B\) 的禁区的话，那么方案数为 \(C_{n+m-2}^{n-1}\)。
就是一共要走 \(n + m - 2\) 步，其中向右走 \(n - 1\) 步，向左走 \(m - 1\) 步，因为随时都能向右走，故方案数为 \(C_{n+m-2}^{n-1}\) 或 \(C_{n+m-2}^{m-1}\)。
考虑禁区时，整个图形可沿 \(x\) 轴或 \(y\) 轴平行的方向切割为两个不包含禁区的矩形。
比如按 \(x = b\) 切割，就可以先算 \((1, 1)\) 到 \((b, y), y\leqslant n - a\) 的方案数，然后再算 \((b, y)\) 到 \((n, m)\) 的方案数，将两个相乘的到的数就是从 \((1, 1)\) 到 \((n,m)\) 且经过 \((b, y)\) 而不经过禁区的方案数。
枚举 \(y\) 即可。
组合数可以提前预处理出阶乘逆元，\(\mathcal{O}(1)\) 计算。
注意：预处理阶乘的逆元时，要处理到 \(n + m\)。
时间复杂度：\(\mathcal{O}(n + m)\)
标签：方案,组合,题解,计数,Grid,ARC058D,禁区 From： https://www.cnblogs.com/Pengzt/p/17743893.html