Help in Problem Asked in Google Online Assessment 2022 (23-07-2022)
source link: http://codeforces.com/blog/entry/105199
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Help in Problem Asked in Google Online Assessment 2022 (23-07-2022)
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
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK