期待値を求める問題では、直接期待値を求めるのではなく、全ての事象に対する答えの総和を求め、事象の場合の数で割ることで期待値を求める手法が有効なことがあります。また逆も然りです。（補足：総和を求める問題で、期待値を考えるのが有効な場合もあるということです。）

この問題でも、全ての塗り方に対するスコアの総和を求め、最後に塗り方の場合の数で割ることとします。さらに、主客転倒と呼ばれるテクニックを用いると、スコアの総和は以下の値が高速に計算できれば \((a,b)\) を全探索することで求まります。

• マス \((a,b)\) が最小長方形に含まれるような塗り方の個数

以下では便宜上塗る \(K\) 個のマスを \((x_1,y_1),(x_2,y_2),\ldots,(x_K,y_K)\) とします。

マス \((a,b)\) が最小長方形に含まれないのは、塗るマスが

• 全ての \(i\ (1\leq i\leq K)\) について \(x_i\) が \(a\) 未満
• 全ての \(i\ (1\leq i\leq K)\) について \(x_i\) が \(a\) より大きい
• 全ての \(i\ (1\leq i\leq K)\) について \(y_i\) が \(b\) 未満
• 全ての \(i\ (1\leq i\leq K)\) について \(y_i\) が \(b\) より大きい

のいずれか一つ以上を満たすときです。これらの条件について包除原理を用いることで、 \(\mathrm{O}(1)\) で マス \((a,b)\) が最小長方形に含まれるような塗り方の個数が求まります。

よって二項係数を求めるための前計算とあわせて \(\mathrm{O}(HW+K)\) でこの問題が解けました。