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