Editorial: Gerald and Giant Chess

We want the number of paths from $(1,1)$ to $(h,w)$ moving only down or right, avoiding $n$ black cells, modulo $M = 10^9+7$.

The grid can be huge ($h,w \le 10^5$), but the number of blocked cells is small ($n \le 2000$). So we should not do DP over all $h\cdot w$ cells.

1) Paths between two points (no obstacles)

From $(r_1,c_1)$ to $(r_2,c_2)$ with $r_1 \le r_2$ and $c_1 \le c_2$, every monotone path consists of

$\Delta r = r_2-r_1$ down moves
$\Delta c = c_2-c_1$ right moves

in any order, so the number of such paths is

$$ \text{ways}((r_1,c_1)\to(r_2,c_2)) = \binom{\Delta r + \Delta c}{\Delta r}. $$

If $r_1 > r_2$ or $c_1 > c_2$ then it is $0$.

2) “Obstacle DP” over special points

Create a list of points:

all black cells $(r_i,c_i)$
plus the destination $(h,w)$

Sort them by $(r,c)$ (row first, then column).

Let the sorted points be $p[0],p[1],\ldots,p[n]$ where $p[n]=(h,w)$ (we appended it).

Define $f[i]$ = number of valid paths from $(1,1)$ to $p[i]$ that do not step on any black cell.

Start with all paths to $p[i]$ ignoring obstacles:

$$ f[i] \leftarrow \text{ways}((1,1)\to p[i]) = \binom{(r_i-1)+(c_i-1)}{r_i-1}. $$

Now subtract paths that hit a black cell. Consider any earlier point $p[j]$ (with $j < i$). If a path reaches $p[j]$ first among all black points on that path, then:

there are $f[j]$ ways to reach $p[j]$ legally,
and then there are $\text{ways}(p[j]\to p[i])$ ways to go from $p[j]$ to $p[i]$.

So we subtract all such contributions:

$$ f[i] = \text{ways}((1,1)\to p[i]) - \sum_{j < i} f[j]\cdot \text{ways}(p[j]\to p[i]) \pmod M. $$

This works because sorting by $(r,c)$ ensures any monotone path can only go from earlier points to later points, and every invalid path has a unique “first” black point it visits.

The answer is $f[n]$ (the value at $(h,w)$).

3) Fast combinations modulo $M$

We need binomial coefficients up to

$$ (h-1)+(w-1) \le h+w. $$

Precompute factorials and inverse factorials:

$\text{fac}[k]=k!\bmod M$
$\text{invfac}[k]=(k!)^{-1}\bmod M$

Then

$$ \binom{N}{K} = \text{fac}[N]\cdot \text{invfac}[K]\cdot \text{invfac}[N-K] \bmod M. $$

(Any standard modular inverse method works; in C++ you typically use $x^{M-2}\\bmod M$ with fast exponentiation since $M$ is prime.)

4) Complexity

Sorting points: $O(n\log n)$
DP transitions: $O(n^2)$, since for each $i$ we loop over $j < i$
Precompute factorials up to $h+w$: $O(h+w)$

With $n\le 2000$, $O(n^2)$ is about $4\cdot 10^6$ operations and is fine.