縦 \(h\) ×横 \(w\) 長方形 \(R\) を固定し、最小長方形が \(R\) になるような黒マスの塗り方が何通りあるか考えてみましょう。

最小長方形が \(R\) であることに必要十分条件は
①全ての黒マスが \(R\) に含まれる
② \(R\) の上辺に黒マスが含まれる
③ \(R\) の下辺に黒マスが含まれる
④ \(R\) の右辺に黒マスが含まれる
⑤ \(R\) の左辺に黒マスが含まれる
の全てを満たすことです。

①を満たすものについて、②～⑤の条件で包除原理を用いることを考えます。 ①を満たすような黒マスの塗り方は \(\binom{hw}{K}\) 通りあります。これを \(f(h,w)\) と表すことにします。

例えば「①を満たし、かつ、②を満たさない」ものは \(f(h-1,w)\) 通り、「①を満たし、かつ、③④を満たさない」ものは \(f(h-1,w-1)\) 通りあります。したがって①～⑤全てを満たすものは

\( f(h,w)\\ -f(h-1,w)-f(h-1,w)-f(h,w-1)-f(h,w-1)\\ +f(h-2,w)+f(h-1,w-1)+f(h-1,w-1)+f(h-1,w-1)+f(h-1,w-1)+f(h,w-2)\\ -f(h-2,w-1)-f(h-2,w-1)-f(h-1,w-2)-f(h-1,w-2)\\ +f(h-2,w-2) \)

通りあることがわかります。これは \(h,w\) のみに依存し、\(R\) の位置に依存しません。これを \(g(h,w)\) とおきます。縦 \(h\) ×横 \(w\) の長方形は 縦 \(H\) ×横 \(W\) の長方形の中に \((H-h+1)(W-w+1)\) 個存在するので、求める答えは

\(\displaystyle \sum_{R}(Rの面積)(最小長方形がRになる確率)\\ =\sum_{h,w}\sum_{Rは縦h×横w}(Rの面積)(最小長方形がRになる確率)\\ =\sum_{h,w}\sum_{Rは縦h×横w}hw\frac{g(h,w)}{\binom{HW}{K}}\\ =\sum_{h,w}(H-h+1)(W-w+1)hw\frac{g(h,w)}{\binom{HW}{K}}\)

となり、\(O(HW+\log MOD)\) の前計算の下で \(O(HW)\) で求めることができます。