Hi guys, I need help with a problem that I've been trying to solve for a while now.

Statement: Given a M x N binary matrix with at most 100000 ones, and given two integers a and b, count the number of zero submatrices with size a x b. Constraints: 1 <= a, b <= M, N <= 10000.

Some more info: The memory and time constraints are 64mb, and 1 sec. Sadly, the problem statement isn't in English, but here's a link to it anyway if you guys want to check it out: http://mendo.mk/Task.do?id=616

Recently I've been reading about matrix multiplication algorithms, more specifically Strassen's algorithm for fast matrix multiplication that runs in O(n^2.81) time as opposed to the standard O(n^3) time for the naive approach. But this speed up comes at a cost, for example we need to pad the matrix with zeroes if n isn't a power of 2, and even though it is asymptotically faster, it also carries a bigger constant factor since it does more additions. Also, it is more memory intensive, and it certainly is harder to implement correctly and optimally.

So my question is: Is the time complexity improvement worth all of these drawbacks in a competitive setting? Are there any problems that are unsolvable with standard matrix multiplication, but are solvable with fast matrix multiplication? And what method do all the best competitors use when they need to multiply 2 matrices?