Let \(S_n\) denote the set of all bijections \(\{1,2,\ldots, n\}\longrightarrow \{1,2,\ldots,n\}\). (An element of \(S_n\) is a permutation.)

---

[1] Connection between a valid \(A\) and permutations

We begin by characterizing a matrix \(A\) that satisfies the conditions.

It is necessary and sufficient that for any \(k\), the set of positions containing integers at most \(k\) will correspond to the target matrix. Let us first consider the set of positions for a fixed \(k\).

Note the number of integers at most \(k\) in each row. Performing row-sort on \(A\) does not change this number. If we then perform column-sort, those numbers for the rows will be rearranged in descending order. Thus, the set of positions containing integers at most \(k\) after performing row-sort and then column-sort will correspond to \(B\) if and only if:

• there exists \(\sigma = \sigma^{(k)} \in S_H\) such that the \(\sigma(i)\)-th row in \(A\) and the \(i\)-th row in \(B\) have the same number of integers at most \(k\).

By considering the similar condition for columns, the condition for \(A\) can be rephrased to the following:

• for each \(k\), there exists \(\sigma^{(k)}\in S_H\) and \(\tau^{(k)}\in S_W\) such that \(A_{ij} \leq k\iff B_{\sigma^{(k)}(i)\tau^{(k)}(j)}\leq k\).

---

[2] Sorting out the condition for permutations

It is easy to count pairs \(\sigma, \tau\) that give the same matrix for each \(k\), so we will count tuples of permutations \(\sigma^{(0)}, \tau^{(0)}\ldots, \sigma^{(9)}, \tau^{(9)}\) that satisfy the condition for some matrix.

It is eventually reduced to counting tuples of permutations \((\sigma^{(0)}, \tau^{(0)}\ldots, \sigma^{(9)}, \tau^{(9)})\) such that:

\(B_{\sigma^{(k)}(i)\tau^{(k)}(j)}\leq k\implies B_{\sigma^{(k+1)}(i)\tau^{(k+1)}(j)}\leq k + 1\).

Consider deciding \(\sigma^{(k+1)}, \tau^{(k+1)}\) when the previous permutations up to \(\sigma^{(k)}, \tau^{(k)}\) are already decided. Then, the number of valid pairs \(\sigma^{(k+1)}, \tau^{(k+1)}\) does not depend on what \(\sigma^{(k)}, \tau^{(k)}\) are. Thus, it is enough to count \(\sigma^{(k+1)}\), \(\tau^{(k+1)}\) when \(\sigma^{(k)}, \tau^{(k)}\) are identity permutations. Therefore, we want to solve the following for each \(k\):

count pairs of permutations \((\sigma, \tau) \in S_H\times S_W\) such that \(B_{ij}\leq k\implies B_{\sigma(i)\tau(j)}\leq k + 1\).

Moreover, for each \(i\) let \(a_i\) be the number of \(j\)’s such that \(B_{ij}\leq k\), and for each \(j\) let \(b_j\) be the number of \(i\)’s such that \(B_{ij}\leq k+1\). Now the problem looks as follows:

given non-increasing sequences \((a_1, \ldots, a_H)\) and \((b_1, \ldots, b_W)\), count pairs of permutations \((\sigma , \tau) \in S_H\times S_W\) such that \(j\leq a_i\implies \sigma(i)\leq b_{\tau(j)}\).

Furthermore, from the non-increasingness of \(b\), we again rephrase it to:

given non-increasing sequences \((a_1, \ldots, a_H)\) and \((b_1, \ldots, b_W)\), count pairs of permutations \((\sigma , \tau) \in S_H\times S_W\) such that \(\sigma(i)\leq b_{\max(\tau(1), \ldots, \tau(a_i))}\).

---

[3] Counting permutations

First, for a fixed sequence \(x = (x_1, \ldots, x_W)\) (\(W\geq x_1\geq \cdots \geq x_W \geq 1\)), let us try to count \((\sigma, \tau)\) such that:

• \(\sigma(i) \leq b_{x_i}\),
• \(\max(\tau(1), \ldots, \tau(a_i)) = x_i\).

We can solve this problem separately for \(\sigma\) and \(\tau\): consider deciding \(\sigma(i)\) and \(\tau(j)\) in ascending order of \(i, j\), then the answer can be expressed as a simple multiplication.

We want to find the sum over all \(x\) of the numbers of \((\sigma, \tau)\), which can be computed by DP where the values of \(x_1, x_2, \ldots\) are decided in this order. The transition from \(x_i\) to \(x_{i+1}\) should involve multiplication by appropriate values that derive from counting \(\tau\), and when \(x_i\) is determined, there should be multiplication by appropriate values that derive from counting \(\sigma\).

From the above, we can perform the counting by a DP with \(O(HW)\) states and \(O(HW+W^3)\) transitions, which can be done in \(O(HW + W^2)\) time using prefix sums.

Performing this computation for each \(k = 0, 1, \ldots, 9\) solves the problem in \(O(HW + W^2)\) time.