Even sum in a matrix

★★★★★

2.9

16 votes

Math Basic, Bitmask, Basic Programming, Bit manipulation, Basics of Bit Manipulation, Bit Manipulation, Math

Details

Submissions

Discussion

Editorial

Problem

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$

Time Limit: 2.5

Memory Limit: 256

Source Limit:

Explanation

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}$

$\begin{pmatrix} 1, 2\\ 4, 5\\ \end{pmatrix}$ , $\begin{pmatrix} 2,3 \\ 5, 6\\ \end{pmatrix}$

Count submatrices = 6.