全単射 \(\{1,2,\ldots, n\}\longrightarrow \{1,2,\ldots,n\}\) の全体を \(S_n\) と書くことにします。（\(S_n\) の元は置換といいます）。

---

[1] 条件を満たす \(A\) と置換の関係

まずは、条件を満たす \(A\) の特徴付けを考えましょう。

任意の \(k\) に対して、\(k\) 以下の整数全体が正しく対応することが必要十分です。まずは \(k\) を固定して、\(k\) 以下の整数の対応について考えることにしましょう。

各行にある \(k\) 以下の整数の個数に注目します。\(A\) に対して行ソートを行っても、各行にある \(k\) 以下の個数は変化しません。その後でさらに列ソートを行うと、各行にある \(k\) 以下の個数は降順に並べ変わります。したがって、\(A\) に行ソート・列ソートをこの順に行った結果、\(k\) 以下の整数が入ったマス全体が \(B\) と一致することは、次と同値です：

• ある \(\sigma = \sigma^{(k)} \in S_H\) が存在して、\(A\) の第 \(\sigma(i)\) 行と \(B\) の第 \(i\) 行にある \(k\) 以下の整数の個数が等しい

列ソートについても同様の条件を考えると、\(A\) が条件を満たすことは次のように言い換えることができます。

• 各 \(k\) に対して、\(\sigma^{(k)}\in S_H\), \(\tau^{(k)}\in S_W\) が存在して、\(A_{ij} \leq k\iff B_{\sigma^{(k)}(i)\tau^{(k)}(j)}\leq k\) が成り立つ

---

[2] 置換の条件の整理

各 \(k\) に対して同じ行列を与える \(\sigma, \tau\) の個数は簡単に数え上げられるので、以下では条件を満たす置換 \(\sigma^{(0)}, \tau^{(0)}\ldots, \sigma^{(9)}, \tau^{(9)}\) を数えることにします。

結局、次を満たす置換の組 \((\sigma^{(0)}, \tau^{(0)}\ldots, \sigma^{(9)}, \tau^{(9)})\) を数え上げる問題に帰着されます：

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

\(\sigma^{(k)}, \tau^{(k)}\) まで決めたときに \(\sigma^{(k+1)}, \tau^{(k+1)}\) を決めることを考えると、条件を満たす \(\sigma^{(k+1)}, \tau^{(k+1)}\) の個数は \(\sigma^{(k)}, \tau^{(k)}\) のとり方に依存しません。したがって、\(\sigma^{(k)}, \tau^{(k)}\) が恒等置換のときに \(\sigma^{(k+1)}\), \(\tau^{(k+1)}\) が数えられればよいです。したがって、各 \(k\) に対して次の問題が解ければよいことが分かります。

置換の組 \((\sigma, \tau) \in S_H\times S_W\) であって、\(B_{ij}\leq k\implies B_{\sigma(i)\tau(j)}\leq k + 1\) を満たすものを数え上げよ。

さらに各 \(i\) について \(B_{ij}\leq k\) となる \(j\) の個数を \(a_i\) とし、各 \(j\) について \(B_{ij}\leq k+1\) となる \(i\) の個数を \(b_j\) とすることで、次の形になります。

単調減少数列 \((a_1, \ldots, a_H)\) および \((b_1, \ldots, b_W)\) が与えられる。置換の組 \((\sigma , \tau) \in S_H\times S_W\) であって \(j\leq a_i\implies \sigma(i)\leq b_{\tau(j)}\) を満たすものを数え上げよ。

さらに \(b\) の単調減少性より、次の形に言い換えます。

単調減少数列 \((a_1, \ldots, a_H)\) および \((b_1, \ldots, b_W)\) が与えられる。置換の組 \((\sigma , \tau) \in S_H\times S_W\) であって \(\sigma(i)\leq b_{\max(\tau(1), \ldots, \tau(a_i))}\) を満たすものを数え上げよ。

---

[3] 置換の数え上げ

まずは、数列 \(x = (x_1, \ldots, x_H)\) （\(W\geq x_1\geq \cdots \geq x_H\geq 1\)）を固定したときに、次を満たす \((\sigma, \tau)\) の個数を求めることを考えてみます。

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

この問題は \(\sigma, \tau\) それぞれ独立に解くことができて、どちらも小さな \(i,j\) に対する \(\sigma(i)\) や \(\tau(j)\) から順に決めていくことを考えるとどちらも単純な掛け算の形になります。

求めるべきは、すべての \(x\) をわたるときの \((\sigma, \tau)\) の総数の総和ですが、\(x_1, x_2, \ldots\) の順に値を決めると考えて、DP で計算することができます。\(x_i\) から \(x_{i+1}\) への遷移するときに \(\tau\) の計算からくる適切な値をかけ、\(x_i\) を定めたら \(\sigma\) の計算からくる適切な値をかければよいです。

以上により目的の数え上げは、状態数 \(O(HW)\)、遷移数 \(O(HW+W^3)\) の DP で計算できることが分かりますが、累積和を用いることで計算量は \(O(HW + W^2)\) 時間にできます。

\(k = 0, 1, \ldots, 9\) についてこの計算を行うことで、本問題は計算量 \(O(HW + W^2)\) 時間で解くことができます。