Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its elements is K.
Example:
$A = \begin{Bmatrix}1&-1\end{Bmatrix}$
$K = 0$
Thus:
$M = \begin{Bmatrix}1 & -1\\-1 & 1\\\end{Bmatrix}$
So, there are 5 submatrices where the sum of its elements is 0:
$ M_{00}...M_{01} = 1 + (-1) = 0$
$ M_{10}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{10} = 1 + (-1) = 0$
$ M_{01}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{11} = (-1) + 1 + (-1) + 1 = 0$
Brute force is obvious and it costs $O(n^4)$, but I'm looking for a less naive solution. The first thing that comes to mind (at least mine) is two pointer algorithm, but it works only when there are no negative members, which is not the case. If it were it would make this question a duplicate of this one.
I believe there is a smarter way to solve this because of the correlation between M and A, but I can't figure out how.