Counting Paths With No Table
A grid has m rows and n columns and NO blocked squares. Starting at the top left and
moving only right or down, count the paths to the bottom right. Print the count modulo
1000000007.
3 rows, 7 columns -> 28
1 row, 200 columns -> 1 there is only one way to walk a corridor
## The table is correct and does not fit
The recurrence is the one from problem 533: dp[i][j] = dp[i-1][j] + dp[i][j-1]. It is right,
and at m = n = 1000000 its table has 10^12 cells. Rolling one row down to O(n) memory
does not save it either, because the time is still m * n.
Nothing is wrong with the reasoning. The constraints are simply outside what any table can reach, and that is a signal in itself: when the bound on a dimension jumps from a few thousand to a million, the intended solution is usually not a table over that dimension.
## Every path is the same length
A path takes exactly m - 1 downward steps and n - 1 rightward steps, in some order, for
m + n - 2 steps in total. A path is therefore nothing more than a CHOICE of which steps are
the downward ones:
answer = C(m + n - 2, m - 1)
This is why problem 533 needs a table and this one does not: an obstacle makes some orders illegal, and then the count stops being a plain choice.
## Computing one binomial coefficient, modulo a prime
C(N, K) = (N * (N-1) * ... * (N-K+1)) / K!
Division is not available modulo p, so multiply by the inverse instead. Since 1000000007
is prime and K! is never a multiple of it at these sizes, Fermat's little theorem gives
inverse(x) = x^(p-2) mod p
computed by repeated squaring in about 30 multiplications.
Use K = min(m-1, n-1), since C(N, K) = C(N, N-K). It halves the loop and, more usefully,
it keeps the loop short when the grid is long and thin.
## Overflow
Two values below 10^9 multiply to nearly 10^18. That fits in a signed 64 bit integer and
does NOT fit exactly in a double, so JavaScript needs big integers or a multiplication that
reduces as it goes.
## Boundaries
A single row or a single column answers 1: there is only one path and C(N, 0) = 1.
A 1 by 1 grid answers 1, the empty path.
## Cost
Time O(min(m, n) + log p). Space O(1).