Number of submatrices with a particular sum
Here is an O(N3) algorithm (it is valid only for matrices of non-negative values).


Compute prefix sums for each column: B[k][j] = Sum(A[0..k][j]).
For each pair of row indices (p, q):
Apply a two-pointers algorithm for implicit array of values B[q][j]-B[p][j].


Where a two-pointers algorithm advances first pointer while sum of values between pointers is less than desired and advances second one when this sum is greater than desired. When the desired sum is found, advance first pointer (x times) while sum does not change and advance second pointer (y times) while sum does not change (we might need to advance pointers more then once in case of sub-matrix column summing to zero), then add x*y to counter of found sub-matrices and continue.