HackerEarth Count the Submatrices problem solution YASH PAL, 31 July 2024 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("%dn",n)#define pll(n) printf("%lldn",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("%dn",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("%dn",ans); return 0;} coding problems solutions