You are given a matrix A having N rows and M columns. The rows are numbered from 1 to N from top to bottom and columns are numbered from 1 to M from left to right. You are allowed to move right and down only, that is if you are at cell (i, j), then you can move to (i+1, j) and (i, j+1). You are not allowed to move outside the matrix.
Your task is to find the number of good path starting from (1,1) to (N,M). Good Path: If the sum of all the elements that lie in the path is divisble by K, then the path is considered as good.
Constraints 1 <= N, M <= 16 1 <= Ai, K <= 10^18
Sample Input 3
3
23
1 2 3
4 5 6
7 8 9
Sample Output 1
Explanation N = 3, M = 3, K = 23 1->2->5->6->9, Sum is 23 which is divisible by 23 and there is only one good path in the above sample matrix, So the output is 1.
I did brute force, and was able to pass some test cases, but I have no idea how to solve it optimally. If anybody can help, it will be appreciated.
It is similar to this problem : https://mirror.codeforces.com/problemset/problem/1006/F (just xor instead of sum)
ok, so almost 3(out of 5) problems were copied ://
(In fact one of the problem was taken from 1 year old OA).
OA for Sde-1 or 6M intership?
2 Month Internships
Through offcampus? or oncampus?
This was a beautiful problem. In this problem you have to use meet in the middle startegy. For each point which is equidistant from (1,1) and (n,m) you have to create two arrays. In the first array you store the value of sum of paths mod k for paths from (1,1) to that point. And in the second array you store the value of sum of paths mod k from that point to (n,m). For each value in the first array you have to find a value in the second array such that their combined sum mod k is zero. You have to sum up the answer for all such equidistant points.