縦 $H$ 横 $W$ のグリッドが与えられる。 このグリッドから一様ランダムに $K$ 個のマスを選ぶ。 選んだマスを被覆するグリッドの各辺に対し平行である長方形のうち、最小の長方形のマスの総数をスコアとする。 スコアの期待値を $\mod 998244353$ で求めよ。
$1 \le H,W \le 10^3 \\ 1 \le K \le HW$
$H=3,W=3,K=2$ について考える。 被覆する最小の長方形は $1 \times 2$ マスと $2 \times 1$ マスのものである。 ここで $1 \times 2$ マスの長方形について議論する。 一番左上の $1 \times 2$ マスの期待値への寄与を考える。 $1\times2$ マスのスコアは $1\times2 = 2$ である。 一番左上の $1\times2$ マスの長方形を作れるのはただ一つしか存在しないため寄与は
$$ \frac{1\times2}{\binom{HW}{K}} $$
となる。 この$1\times 2$ マスの長方形の置き方のパターン数だけ全体の期待値に寄与する。 この$1\times2$ マスは $(H-1+1) \times (W-2+1)$ 通りにおけるので期待値の寄与は以下の通りになる。
$$ \frac{1\times2\times(H-1-+1)\times(W-2+1)}{\binom{HW}{K}} $$
これを一般化していけば解けることが分かる･･･わけではない。
一番左上の $1\times2$ マスの長方形を作れるのはただ一つしか存在しないため
一番左上の $1\times2$ マスの作り方はただ一つしか存在しないのでこの考え方が適用できた。 $4\le K$ の場合を考える。 $K$ 個のマスの中で一番上にあるマスが上辺、左にあるマスが左辺、下にあるマスが下辺、右にあるマスが右辺の座標になることがわかる。 縦の長さを $r$ 横の長さを $c$ とする。 これの通り数は単純に $\binom{rc}{K}$ とはならない。$rc$ 個の中から $K$ 個選んだ中で必ずしも一番上にある列にマスが置かれるとは限らないからだ。 これは余事象の考え方を使えば通り数を求められる。 一番端の上下左右どれか一つでも 含まない 通り数を求めて、そこから$\binom{rc}{K}$ から引けばよい。
$$ r \times c マスとなるようにマスを置くには上下左右の端全てに配置しなければならない \\\\ \ \iff 上下左右の端どれか一方向でもマスが配置されていないと r \times c は作れない $$
縦横それぞれの長方形について期待値の寄与を求めて、その総和を $\binom{HW}{K}$ で割ればよい。 が、含まない通り数を求めるパートがかなり難しい。 これは包除原理を使う。
https://manabitimes.jp/math/611
つまり
$$ \begin{align*} &\binom{rc}{K} \\ &- \left\{ \binom{(r-1)c}{K} \times 2 + \binom{r{c-1}}{K} \times 2 \right\} &\\ &+ \left\{ \binom{(r-1)(c-1)}{K} \times 4 + \binom{(r-2)c}{K} + \binom{r(c-2)}{K} \right\} \\ &- \dots \end{align*} $$