Paths With a Divisible Sum
Walk from the top-left cell to the bottom-right cell, moving only RIGHT or DOWN. A
path's score is the total of every cell it visits, including both ends. Count the paths
whose score is divisible by k.
Print the count modulo 1000000007.
5 2 4
3 0 5 k = 3 -> 2
0 7 2
## Why the position is not enough
Problem 532 counts paths and needs only the cell. Here two paths reaching the same cell are NOT interchangeable: one may be extendable to a divisible total and the other not, depending on what each has collected so far.
So the state has to carry something about the score. Carrying the score itself is hopeless, since it ranges over the sum of the whole grid.
## Carry the residue
The question only ever asks whether the final total is divisible by k, and that depends on
the running total only through its REMAINDER:
dp[r][c][t] = how many paths reach (r, c) with running total congruent to t mod k
The state records exactly what the objective can distinguish, and no more. Two running totals with the same remainder behave identically for the rest of the walk, so they merge.
Same principle as problem 492's residue state for subsets, applied to a grid.
## The transition
dp[r][c][ (t + g[r][c]) mod k ] += dp[r-1][c][t] + dp[r][c-1][t]
or equivalently, reading rather than pushing:
dp[r][c][t] = dp[r-1][c][(t - g[r][c]) mod k] + dp[r][c-1][(t - g[r][c]) mod k]
The subtraction has to be taken modulo k and made non-negative first, which in most
languages means ((t - v) % k + k) % k. Python's % already returns a non-negative value,
so a solution prototyped there and ported can fail on exactly this line.
## The answer
dp[m-1][n-1][0]. Residue 0 means divisible, and the destination cell's own value must
already be included, which is why the base case is
dp[0][0][g[0][0] mod k] = 1 rather than dp[0][0][0] = 1.
Forgetting that the START cell counts is the other common error. 1 as a one-cell grid with
k = 1 answers 1 and with k = 2 answers 0, and that pair catches it.
## Boundaries
0 0 / 0 0 with k = 5 answers 2: every path sums to 0, which is divisible by anything,
so both paths qualify.
2 2 2 / 2 2 2 / 2 2 2 with k = 2 answers 6: every path visits 5 cells summing to 10, so
all six paths qualify.
## Cost
Time O(m n k). Space O(n k) with two rows.