You are given a matrix \(A\) containing \(N \times M\) elements. You are required to find the number of rectangular submatrices of this matrix such that the sum of the elements in each such submatrix is even.
Input format
- The first line of input given two numbers \(N\ and\ M\) denoting the dimensions of the matrix.
- The next \(N\) lines contain space-separated \(M\) numbers.
Output format
Print a number denoting the number of rectangular submatrices, the sum of the elements of each is even.
Constraints
\(1≤N,M≤2000\)
\(1≤A_i,_j≤10^9\), \(1≤i≤N,1≤j≤M\)
2 3 1 2 3 4 5 6
6
The following sub-matrices are suitable for us:
\(\begin{pmatrix} 2 \end{pmatrix}\), \(\begin{pmatrix} 4 \end{pmatrix}\),\(\begin{pmatrix} 6 \end{pmatrix}\),\(\begin{pmatrix} 1,2,3 \end{pmatrix}\)
Count submatrices = 6.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor