# HackerEarth Count the Submatrices problem solution

In this HackerEarth Count the Submatrices problem solution A matrix of size M x N where M and N are integers that denote the number of rows and columns of the matrix respectively. The matrix contains integer elements only. You are given an integer P. Write a program to determine the number of submatrices of this matrix such that the sum of all the elements of a submatrix is divisible by P.

## HackerEarth Count the Submatrices problem solution.

`#include<iostream>#include<cmath>#include<cstring>#include<string>#include<bitset>#include<algorithm>#include<vector>#include<set>#include<map>#include<stack>#include<stdio.h>#include<queue>#define si(n) scanf("%d",&n)#define sll(n) scanf("%lld",&n)#define mod 1000000007 // 10**9 + 7#define INF 1e9#define FOR(i,a,b) for(int (i) = (a); (i) < (b); ++(i))#define RFOR(i,a,b) for(int (i) = (a)-1; (i) >= (b); --(i))#define CLEAR(a) memset((a),0,sizeof(a))#define mp(a, b) make_pair(a, b)#define pb(a) push_back(a)#define rep(i, a, b) for (int i = a; i < b; i++)#define rrep(i, b, a) for (int i = b; i > a; i--)#define all(v) v.begin(), v.end()#define GETCHAR getchar_unlocked#include<assert.h>#define pi(n) printf("%d\n",n)#define pll(n) printf("%lld\n",n)#define rk() int t; scanf("%d",&t); while(t--)using namespace std;const double pi = acos(-1.0);const int er[8] = {-1,-1,0,1,1,1,0,-1};const int ec[8] = {0,1,1,1,0,-1,-1,-1};const int fr[4] = {-1,1,0,0};const int fc[4] = {0,0,1,-1};typedef unsigned long long ull;typedef long long ll;typedef long l;typedef pair<int,int> pii;typedef vector<int> vec;typedef vector<pii> vpii;ll po(ll a,ll p){ll ret = 1;while(p){if(p&1)ret = (ret*a)%mod;a=(a*a)%mod;p=p>>1;}return ret%mod;}int a[205][205];int s[205];int main(){  int n,m,p;  scanf("%d%d%d", &m, &n, &p);  for(int i=0;i<m;i++){    for(int j=0;j<n;j++){      scanf("%d", &a[i][j]);    }   }  int ans = 0;  for(int i=0;i<m;i++){    for(int j=0;j<n;j++)s[j] = 0;    for(int j=i;j<m;j++){      int t[205]={0};      t[0]=1;      for(int k=0;k<n;k++)s[k]+=a[j][k];      int sum=0;      for(int k=0;k<n;k++){        sum=(sum+s[k])%p;        ans+=t[sum]++;      }    }  }  printf("%d\n",ans);  return 0;}`

### second solution

`#include<bits/stdc++.h>using namespace std;#define vi vector < int >#define pii pair < int , int >#define pb push_back#define mp make_pair#define ff first#define ss second#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )#define ll long long#define llu unsigned long long#define MOD 1000000007#define INF 0x3f3f3f3f#define dbg(x) { cout<< #x << ": " << (x) << endl; }#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }#define dbg3(x,y,z) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << " , " << #z << ": " << (z) << endl; }#define all(x) x.begin(),x.end()#define mset(x,v) memset(x, v, sizeof(x))#define sz(x) (int)x.size()int a[201][201];int s[201][201];int v[201];int c[201];int brute(int n,int m,int p){    int i,j,k,l;    for(i=1; i<=n; i++)    {        for(j=1; j<=m; j++)        {            s[i][j] = a[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];            s[i][j] %= p;            if(s[i][j] < 0)                s[i][j] += p;        }    }    int ans = 0;    for(i=1; i<=n; i++)    {        for(j=1; j<=m; j++)        {            for(k=i; k<=n; k++)            {                for(l=j; l<=m; l++)                {                    int x = s[k][l] - s[k][j-1] - s[i-1][l] + s[i-1][j-1];                    x %= p;                    if(x < 0)                        x += p;                    if(x == 0)                    {                        ans++;                    }                }            }        }    }    return ans;}int solve(int n,int m,int p){    int i,j,k;    int ans = 0;    for(i=0;i<n;i++)    {        mset(v,0);        for(j=i;j<n;j++)        {            mset(c,0);            for(k=0;k<m;k++)            {                v[k] += a[j][k];                v[k] %= p;            }            int sum = 0;            for(k=0;k<m;k++)            {                sum += v[k];                sum %= p;                c[sum]++;            }            int tmp = 0;            for(k=0;k<p;k++)            {                if(k == 0)                    tmp += (c[k]*(c[k]+1))/2;                else                    tmp += (c[k]*(c[k]-1))/2;            }            ans += tmp;        }    }    return ans;}int main(){    int n,m,p;    int i,j;    scanf("%d%d%d",&n,&m,&p);    assert(1 <= n && n <= 200);    assert(1 <= m && m <= 200);    assert(1 <= p && p <= 200);    for(i=0;i<n;i++)    {        for(j=0;j<m;j++)        {            scanf("%d",&a[i][j]);            assert(1 <= a[i][j] && a[i][j] <= 200);        }    }    int ans = solve(n,m,p);    printf("%d\n",ans);    return 0;}`