Hints: Gerald and Giant Chess

Ignore the black cells for a moment. How many monotone paths are there from $(1,1)$ to $(r,c)$ if you can only move down or right?

Answer to Hint 1:
Any path from $(1,1)$ to $(r,c)$ makes exactly $(r-1)$ down moves and $(c-1)$ right moves, in any order. So the count is a binomial coefficient:

$$ \binom{(r-1)+(c-1)}{r-1}. $$

Now bring back black cells. If you try to do DP over all $h \\times w$ cells, what blocks you from doing that directly?

Answer to Hint 2:
$h$ and $w$ can be up to $10^5$, so a full grid DP is too large. But the number of black cells is only $n \\le 2000$.

Try to build a DP that only “cares” about a small set of special cells. Which cells are special enough to matter besides the black ones?

Answer to Hint 3:
Besides the $n$ black cells, the destination $(h,w)$ is special (it’s what we want to reach). Consider the set of points:

• all black cells,
• plus $(h,w)$.

Sort these points by row, then by column. Why does this ordering help when you want to count paths that go through earlier points?

Answer to Hint 4:
With moves only down/right, a path can go from point $j$ to point $i$ only if $r_j \\le r_i$ and $c_j \\le c_i$. Sorting by $(r,c)$ makes it natural to consider transitions from earlier to later points.

Let $f[i]$ be the number of valid paths from $(1,1)$ to point $i$ that avoid all black cells. Start with the number of all paths to $i$ (ignoring blocks). How can you subtract paths that are invalid because they visit a black cell?

Answer to Hint 5:
Every invalid path to point $i$ has a first black cell (in sorted order) that it visits among your list of special points. If that first visited black cell is point $j$, then:

• there are $f[j]$ valid ways to reach $j$ (without stepping on black cells),
• and there are

$$ \binom{(r_i-r_j)+(c_i-c_j)}{r_i-r_j} $$

ways to go from $j$ to $i$.

So you can subtract contributions of earlier points:

$$ f[i] = \\text{ways}(1,1 \\to i) - \\sum_{jwhere terms with $r_j > r_i$ or $c_j > c_i$ contribute $0$.

Now you just need to compute binomial coefficients modulo $10^9+7$ quickly.

What maximum value of $(r-1)+(c-1)$ (or $(r_i-r_j)+(c_i-c_j)$) do you ever need, and how can you precompute factorials and inverse factorials up to that?

Answer to Hint 7:
You need combinations up to about $h+w$ (at most $(h-1)+(w-1)$). Precompute:

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

for $k=0..h+w$, then

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

Finally, after you append $(h,w)$ as the last “special point”, the answer is just $f[\\text{dest}]$.