2435. Paths in Matrix Whose Sum Is Divisible by K Hard

1/**
2 * [2435] Paths in Matrix Whose Sum Is Divisible by K
3 *
4 * 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.
5 * 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 10^9 + 7.
6 *  
7 * <strong class="example">Example 1:
8 * <img src="https://assets.leetcode.com/uploads/2022/08/13/image-20220813183124-1.png" style="width: 437px; height: 200px;" />
9 * Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
10 * Output: 2
11 * Explanation: There are two paths where the sum of the elements on the path is divisible by k.
12 * The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
13 * The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.
14 * 
15 * <strong class="example">Example 2:
16 * <img src="https://assets.leetcode.com/uploads/2022/08/17/image-20220817112930-3.png" style="height: 85px; width: 132px;" />
17 * Input: grid = [[0,0]], k = 5
18 * Output: 1
19 * Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.
20 * 
21 * <strong class="example">Example 3:
22 * <img src="https://assets.leetcode.com/uploads/2022/08/12/image-20220812224605-3.png" style="width: 257px; height: 200px;" />
23 * Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
24 * Output: 10
25 * Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	m == grid.length
31 * 	n == grid[i].length
32 * 	1 <= m, n <= 5 * 10^4
33 * 	1 <= m * n <= 5 * 10^4
34 * 	0 <= grid[i][j] <= 100
35 * 	1 <= k <= 50
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/
41// discuss: https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn number_of_paths(grid: Vec<Vec<i32>>, k: i32) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2435() {
59    }
60}
61