Hard
You are given a 0-indexed m x n
integer matrix grid
and an integer k
. You are currently at position (0, 0)
and you want to reach position (m - 1, n - 1)
moving only down or right.
Return the number of paths where the sum of the elements on the path is divisible by k
. Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: There are two paths where the sum of the elements on the path is divisible by k. The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3. The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.
Example 2:
Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.
Example 3:
Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 104
1 <= m * n <= 5 * 104
0 <= grid[i][j] <= 100
1 <= k <= 50
import java.util.Arrays;
public class Solution {
private int[][] p = new int[50005][50];
private int[][] r = new int[50005][50];
public int numberOfPaths(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int x = 0;
for (int i = 0; i < n; ++i) {
Arrays.fill(r[i], 0, k, 0);
x += grid[0][i];
r[i][x % k] = 1;
}
for (int i = 1; i < m; ++i) {
int[][] t = p;
p = r;
r = t;
x = grid[i][0] % k;
for (int j = 0; j < k; ++j) {
r[0][(x + j) % k] = p[0][j];
}
for (int j = 1, pj = 0; j < n; ++j, ++pj) {
x = grid[i][j] % k;
int y = (x > 0) ? (k - x) : 0;
for (int l = 0; l < k; ++l, ++y) {
if (y == k) {
y = 0;
}
int modulo = 1000000007;
r[j][l] = (p[j][y] + r[pj][y]) % modulo;
}
}
}
return r[n - 1][0];
}
}