593. 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).
Constraints - `1 ≤ m ≤ 1000000` - `1 ≤ n ≤ 1000000`
Input
One line containing two integers m and n, the number of rows and columns.
Output
Print one integer, the number of paths, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.