# HackerEarth Even sum in a matrix problem solution

In this HackerEarth Even sum in a matrix problem solution You are given a matrix A containing N X 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.

## HackerEarth Even sums in a matrix problem solution.

`#include<bits/stdc++.h>using namespace std;int n,m;int sum[2002][2002],a[2002][2002];bitset<2002> bt[2002];int main(){    ios_base::sync_with_stdio(false);    cin.tie(NULL);    cout.tie(NULL);        cin >> n >> m;        for(int i=0;i<n;i++){                for(int j=0;j<m;j++){                cin >> a[i][j];                        sum[i+1][j+1]=a[i][j]%2;                }        }        for(int i=1;i<=n;i++){                for(int j=1;j<=m;j++){                        sum[i][j]+=sum[i][j-1];                }        }        for(int i=1;i<=n;i++){                for(int j=1;j<=m;j++){                        sum[i][j]+=sum[i-1][j];                        sum[i][j]%=2;                        bt[i][j]=sum[i][j];                }        }        long long sol=0;        for(int i=0;i<n;i++){                for(int j=i+1;j<=n;j++){                        int c= ( bt[i] ^ bt[j]).count();                        int d= m+1-c;                        sol += c*1ll*(c-1)/2;                        sol += d*1ll*(d-1)/2;                }        }        cout<<sol<<endl;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAX_N = 2e3 + 14;bitset<MAX_N> table[MAX_N];int main() {    ios::sync_with_stdio(0), cin.tie(0);    int n, m;    cin >> n >> m;    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            int x;            cin >> x;            table[i + 1][j + 1] = table[i + 1][j] ^ table[i][j] ^ table[i][j + 1] ^ x % 2;        }    }    ll ans = 0;    for (int i = 0; i <= n; ++i) {        for (int j = 0; j < i; ++j) {            int c = (table[i] ^ table[j]).count();            ans += c * (c - 1) / 2 + (m - c + 1) * (m - c) / 2;        }    }    cout << ans << '\n';}`