I have an array $A[]$ of N elements ($N<=1000$, $-1000<=A[i]<=1000$). We define a Matrix M such that $M[i,j]= A[i]*A[j]$. In the resulting matrix $M$, we have to count the number of submatrices with sum $K$.
Here is what I came up with: We can maintain a cumulative matrix DP such that $DP[i,j]$ saves the cumulative sum of elements from $M[0,0]$ to $M[i,j]$. Now using this $DP$ matrix we can get the sum of any submatrix in $O(1)$ using inclusion-exclusion. So we can iterate through all submatrices and see which ones sum to $K$. Complexity of my solution is $O(N^4)$. I know there should be a way to do this in $O(N^2)$ by exploiting the property that $M$ was formed from $A$.
I'd be glad if someone could point me to a $O(N^2)$ solution. Can we do it better than $O(N^2)$?
The sum of the submatrice consisting of rows $i_1$ through $i_2$ and columns $j_1$ through $j_2$ is basically
$$(\sum_{i=i_1}^{i_2} A[i]) \times (\sum_{j=j_1}^{j_2} A[j])$$
From this property, we can construct an $O(N+K)$ solution (there are many alternative solutions, of course, for example, we can also do this in $O(d(K) N)$).
Edit: OP asked how to do this in $O(N^2 \log N)$:
In $O(N^2)$ time, for every pair $i_1, i_2$, count $\sum_{i=i_1}^{i_2} A[i]$. Sort these numbers. For every number $x$ in this sorted list, count the number of $K/x$ that are present in this list -- each pair found is a submatrice.