На контесте немного не успел отдебагать, но в дорешивании сдал за O(n³*log(P)), где P - максимальный элемент в матрице. 
Общая идея такова: сначала как и в написанных выше решениях рассматривается максимальный элемент, тогда задача сводится к подсчету числа способов расставить числа от 0 до P в фигуре типа уголка, так чтобы максимум в каждой строке и столбце был P.
Найдем это число при помощи формулы включений и исключений.

Пусть уголок имеет размерности как на рисунке.

Тогда посчитаем число способов расставить числа от 0 до P, так чтобы какие-то i строк были плохими (т.е. максимум в строке < P), и какие-то j столбцов были плохие.
Таких способов понятно F(i,j)=P^c1*(P+1)^c2, где c1=i*a+j*b-i*j, c2=x*a+y*b-x*y-c1 (в этих i cтроках и j столбцах должны стоять числа меньше P, а в остальных клетках могут стоять числа от 0 до P, с1, с2 - количества клеток этих двух видов). Но тогда ответ это просто сумма этих выражений по всем возможным выборкам i строк и j столбцов, при этом F(i,j) входит со знаком "+", если сумма i и j четна и с "-" в противном случае. Но понятно, что выборок i строк и j столбцов ровно C(x,i)*C(y,j), где С(n,k)-биномиальный коэффициент.
Все, таким образом для уголка можно посчитать ответ за O(n²*log(P)) просто пройдя двумя циклами по i и по j и добавив или отняв F(i,j)*C(x,i)*C(y,j). Также понятно, что общая сложность O(n³*log(P)) так как различных элементов в строках и столбцах O(n).

Исходный код: http://pastebin.com/rFnZ5tPh