HDU 5245：Joyful——矩陣隨機子矩陣覆蓋期望值計算

題目大意

M×N矩陣，每次隨機均勻選兩個格子(x1,y1)、(x2,y2)，以其為對角線覆蓋子矩陣。重複K次（K≤20）。求最終被覆蓋格子數的期望值，四捨五入取整。

核心思路：單格子被覆蓋概率的獨立性與線性期望

由期望的線性性，總期望 = ∑_所有格子 P(該格子被覆蓋至少一次)。
單次操作中，格子(i,j) 不被覆蓋 的條件：兩個隨機格子都落在其「不覆蓋區域」。

不覆蓋區域劃分與計數

格子(i,j)將矩陣分為9個區域（以其為中心的3×3網格）：

• 四角：左上、右上、左下、右下
• 四邊：上、下、左、右（不含角）
• 中心：格子自身

兩個隨機點都不覆蓋(i,j)，當且僅當它們落在同一側（都在上方、都在下方、都在左側、都在右側），但需排除雙重計算的四角區域。
令總格子數tot = M*N，單次采樣總方案數tot^2。
格子(i,j)單次不被覆蓋方案數：

up      = (i-1)*N          // 上方格子數
down    = (M-i)*N          // 下方
left    = (j-1)*M          // 左側
right   = (N-j)*M          // 右側
lu      = (i-1)*(j-1)      // 左上角
ru      = (i-1)*(N-j)      // 右上角
ld      = (M-i)*(j-1)      // 左下角
rd      = (M-i)*(N-j)      // 右下角

ans = up^2 + down^2 + left^2 + right^2
    - lu^2 - ru^2 - ld^2 - rd^2  // 容斥原理扣除四角重複

單次不覆蓋概率p = ans / tot^2。
K次獨立操作後不被覆蓋概率p^K。
被覆蓋概率1 - p^K。
累加所有格子得期望，最後+0.5取整（四捨五入技巧）。

關鍵實現細節

• tot^2可能超64位（M,N≤500 → tot≤250000 → tot^2≤6.25e10），用long long（或double直接算概率）。
• 雙層循環遍歷所有格子 O(MN)，K≤20，pow(p, K)用標準庫pow或快速冪。
• 樣例：3×3 K=1 → 期望≈3.5679 → 輸出4；4×4 K=2 → 輸出8。

參考代碼框架 (C++)

總結
本題巧妙運用「期望線性性」將問題分解為單格子覆蓋概率，利用幾何劃分與容斥原理計算單次不覆蓋方案數，再用獨立重複試驗概率公式得出K次覆蓋概率。避免了直接模擬2^(MN)的指數複雜度。