条件整理

与えられた等式の左辺を \(L\coloneqq \min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}\) ，右辺を \(R\coloneqq \max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}\) とします.

左辺の \(\min\) を達成する \(i\) と，右辺の \(\max\) を達成する \(j\) を取ります. このとき \(L\ge A_{i,j}\ge R\) が成り立ちます. したがって，一般に \(L\ge R\) であり， \(L=R\) となる条件は \(L\le R\) であると言い換えられます.

上述の \(i,j\) において \(L=R\) という条件を考えると，

\[\max_{1\le q\le W}A_{i,q}=A_{i,j}=\min_{1\le p\le H}A_{p,j}\quad \cdots(\ast)\]

が成り立つことが分かります. 逆に，このような \(i,j\) が存在することが必要十分です.

包除原理による表式

そのような \(i,j\) が存在しないようなものを数えて，全体から引くことを考えます. そして，すべての \(i,j\) に対して \((\ast)\) が成り立たないという条件を包除原理で展開します. いくつかの \((i,j)\) が指定されたとき，これらすべてが \((\ast)\) を満たすような \(A\) の個数を数え上げたいです. \((i,j),(p,q)\) が \((\ast)\) を満たすとき，\((i,q),(p,j)\) も \((\ast)\) を満たすことが確認できます. したがって，重要なのは指定された \((i,j)\) の集合ではなく，それに含まれる \(i\) の集合および \(j\) の集合の組，ひいては \(i,j\) の種類数であるということです.

\(i,j\) の種類数がそれぞれ \(h,w\ge 1\) であるとします. このとき，包除原理による係数の総和は

\[ \sum_{a=0}^{h}\sum_{b=0}^{w}(-1)^a(-1)^b\binom{h}{a}\binom{w}{b}\sum_{k=0}^{(h-a)(w-b)}\binom{(h-a)(w-b)}{k}(-1)^k \]

と表せます. ここで，\(i,j\) の種類数がそれぞれ \(h,w\) であるという条件を表すために別の包除原理が入っています. 本題の包除原理の係数は最後の \((-1)^k\) という項です. 結局のところ \(a=h\) または \(b=w\) のときだけ \(3\) つ目の \(\Sigma\) が \(1\) となり，他の場合は \(0\) となります. \(0^0=1\) に注意してください. 結局，この総和は \(-(-1)^{h+w}\) です. さて，\(h=w=0\) の場合も含めて，これを全体から引くことにしたことを思い出すと，答えへの寄与としては，包除原理による係数の総和は \((-1)^{h+w}\) であることが分かります.

整数 \(m\in [1,M]\) を固定し，\(L=R=m\) である \(A\) の条件を考えます. \((\ast)\) を満たす \(i\) および \(j\) の集合としてそれぞれ \(h\) 行 \(w\) 列が指定されたとします. これらの交点では \(A_{i,j}=m\) となります. また，行 \(i\) のみ・列 \(j\) のみに注目すると \(A_{i,q}\le m, A_{p,j}\ge m\) が条件となります. 指定された行にも列にも属さない点では \(A_{p,q}\) は任意の値を取ることができます. 以上を踏まえると，答えは

\[ \sum_{h=1}^{H}\sum_{w=1}^{W}\sum_{m=1}^{M}\binom{H}{h}\binom{W}{w}(-1)^{h+w}m^{h(W-w)}(M+1-m)^{(H-h)w}M^{(H-h)(W-w)} \]

と表せます. この値を高速に計算します.

ラグランジュ補間による計算

\(\sum\) の中身の \(M\) は定数と見て固定し，\(\sum\) の上端の \(M\) のみを変数とすることで，答えを \(M\) の多項式と見なします. （中身の \(M\) も変数と見ても多項式にはなりますが，計算上の都合が悪いです. ）次数は高々 \(HW\) です. そこで，その多項式を（陰に）求めることを考え，ラグランジュ補間を用います.

答えの \(3\) 重 \(\Sigma\) のうち\(\sum_{m}\) を外に出し，内側を抜き出して，

\[ f(m)=\sum_{h=1}^{H}\sum_{w=1}^{W}\binom{H}{h}\binom{W}{w}(-1)^{h+w}m^{h(W-w)}(M+1-m)^{(H-h)w}M^{(H-h)(W-w)} \]

と定めます. 二項定理を用いると

\[ \begin{aligned} f(m)&=\sum_{h=1}^{H}\binom{H}{h}(-1)^h\sum_{w=1}^{W}\binom{W}{w}(-(M+1-m)^{H-h})^w(m^hM^{H-h})^{W-w}\\ &=\sum_{h=1}^{H}\binom{H}{h}(-1)^h\Big[(-(M+1-m)^{H-h}+m^hM^{H-h})^W-(m^hM^{H-h})^W\Big] \end{aligned} \]

と変形できます. よって，与えられた \(m\) に対して \(f(m)\) を \(O(H\log(HW))\) time などで計算できます.

答えは \(F(M)=\sum_{m=1}^{M}f(m)\) であり，これを \(M\) の多項式とみなします. \(F(0),F(1),\dots, F(HW)\) を得ることができれば，\(F(M)\) をラグランジュ補間で計算できます. これらの計算は結局 \(f(1),f(2),\dots, f(HW)\) の計算に帰着します.（ここで \(f\) が \(M\) に依存するとこの議論はできないことに注意してください. ）ラグランジュ補間自体は，適当な階乗テーブルの前計算のもと，多項式の次数に対して線形時間で行うことができます.

以上の解法は \(O(H^2W\log(HW))\) time などで動作します.