Paths in Matrix Whose Sum Is Divisible by K

Track only the remainder

Let dp[r][c][rem] be the number of paths to cell (r,c) whose sum modulo k is rem. The start cell contributes grid[0][0] mod k. For every other cell, combine each reachable remainder from its top and left predecessors, add the current value, and place the count into the new remainder. Return the count at the bottom-right cell with remainder zero, applying the requested modulus to counts.

The invariant is that every legal monotone path to a cell is counted once by its final remainder. Time is O(rows * cols * k) and space is O(rows * cols * k), reducible to O(cols * k) with rolling rows when reconstruction is not needed. Test a one-cell matrix, k = 1, negative values if allowed (normalize modulo), and grids with only one route. Do not carry exact sums when only divisibility matters; that creates a state dimension based on value magnitude rather than k.