[1] Organize the conditions

Let’s try various matrices satisfying the conditions by hand (or observe the ones enumerated by writing a program) and organize what kind of conditions they are.

Consider writing \(0\) or \(1\) in undetermined cells, and the following conditions can be found.

• If there is a \(1\) to the left of \(0\), the squares below the \(0\) must also be \(0\):
  
  • because if there were a \(1\) below, that would make four squares not satisfying the inequality.
    
• If there is a \(1\) to the right of \(0\), the squares above the \(0\) must also be \(0\).
  
• If there is a \(1\) above \(0\), the squares to the right of the \(0\) must also be \(0\).
  
• If there is a \(1\) below \(0\), the squares to the left of \(0\) must also be \(0\).
  

Conversely, matrices that satisfy these conditions are the ones to be counted.

[2] Remove parts unrelated to the conditions

If there is a \(1\) to the left and right of \(0\), the entire column will be \(0\).

Let’s focus on this column consisting only of \(0\). If you select four cells related to this column (when you choose this column for \(b\) or \(d\)), the inequality will always hold.

Therefore, whether the matrix satisfies the conditions or not is determined by the matrix when this column is removed. So, let’s remove the columns consisting only of \(0\) in advance.

For \(m = 1, 2, \dots, M\), we need to find the following. (After that, multiply it by the binomial coefficient \(\binom Mm\) for which columns are removed, and sum the results.)

• The number of \(N \times m\) matrices consisting of \(\lbrace 0, 1 \rbrace\) that satisfy the following conditions:
  • There is a \(1\) in each column.
  • \(A_{a,b} \times A_{c,d} ≤ A_{a,d} \times A_{b,c}\ (a < c,\ b < d)\).

The conditions in [1] are changed as follows.

• If there is a \(1\) to the left of \(0\), the squares to the lower right of the \(0\) must also be \(0\).
  
• If there is a \(1\) to the right of \(0\), the squares to the upper left of the \(0\) must also be \(0\).
  
• If there is a \(1\) above \(0\), the squares to the right of the \(0\) must also be \(0\).
  
• If there is a \(1\) below \(0\), the squares to the left of the \(0\) must also be \(0\).
  

---

The row consisting only of \(0\) is also unrelated to the conditions, so let’s remove it in advance as well.

For all combinations of \(n = 1, 2, \dots, N\) and \(m = 1, 2, \dots, M\), we need to find the following. (After that, multiply it by the binomial coefficient \(\binom Nn\binom Mm\) for which row and column are removed, and sum the results.)

• The number of \(n \times m\) matrices consisting of \(\lbrace 0, 1 \rbrace\) that satisfy the following conditions:
  • There is a \(1\) in each row.
  • There is a \(1\) in each column.
  • \(A_{a,b} \times A_{c,d} ≤ A_{a,d} \times A_{b,c}\ (a < c,\ b < d)\).

The conditions in [1] are changed as follows.

• If there is a \(1\) to the left of \(0\), the squares to the lower right of the \(0\) must also be \(0\).
  
• If there is a \(1\) to the right of \(0\), the squares to the upper left of the \(0\) must also be \(0\).
  
• If there is a \(1\) above \(0\), the squares to the lower right of the \(0\) must also be \(0\).
  
• If there is a \(1\) below \(0\), the squares to the upper left of the \(0\) must also be \(0\).
  

These four conditions can be organized and aggregated into the following single condition.

• If there are two \(1\)s to the top left and bottom right, the squares in the rectangular area between them must also be \(1\). (★)
  

[3] Observe the shape of matrices satisfying the conditions

By observing the shape of the matrix that satisfies the conditions, we can see two zigzag lines drawn from the bottom left to the top right; the area between them is filled with \(1\)s, and the other areas with \(0\)s.

Here, note that there must be a \(1\) in each row/column. In other words, when the two zigzag lines meet, they must separate immediately.

It is clear that this shape is a sufficient condition since it satisfies (★), and one can show from (★) that it is necessary.

[4] Count the number of matrices using dynamic programming

When \(n, m\) are fixed, the number of matrices of this shape can be found by the following DP:

\(\text{dp}[i][l][r] := {}\)(The number of ways to write numbers that satisfy the conditions for the top \(i\) rows such that the \(l\)-th to \(r\)-th columns are filled with \(1\)s in the \(i\)-th row).

It takes \(O(nm^4)\) time to calculate this naively, but it can be done in \(O(nm^2)\) time using cumulative sums.

After that, calculate this for all \(n, m\), multiply by the appropriate coefficients, and add them up. This will take \(O(N^2M^3)\) time as is, but notice the following.

• The transitions in the DP are computed only by multiplication and addition.
• The calculation in DP for certain \(n, m\) is part of the calculation for \(n = N, m = M\).
• The coefficient of the contribution of the result of the DP calculation to the answer, \(\binom Nn\binom Mm\), can be decomposed into a part related to \(n\) and another related to \(m\).

Then, we can accumulate the calculations for all \(n, m\) and do them simultaneously. This enables us to solve this problem in \(O(NM^2)\) time.

Sample Implementation (C++)

(Above is a modification of a translation by GPT-4.)