東西でテントを張る個数を \(x\) 、南北を \(y\) 、それ以外で独立して張る個数を \(z\) とします。

• まず、縦 \(H\) 行から \(z\) 行、横 \(W\) 列から \(z\) 列を選び、その中で \(z!\) 通りの位置と \(4^z\) 通りの東西南北を選びます。
• 残り \(H-z\) 行 \(W-z\) 列から東西にテントを張る \(x\) 行 \(2x\) 列を選びます。
• 残り \(H-z-x\) 行 \(W-z-2x\) 列から南北にテントを張る \(2y\) 行 \(y\) 列を選びます。
• ただし、何も選ばない \(x=y=z=0\) のとき余分に数えた \(1\) 通りを引きます。

よって、答えは \(\begin{aligned} \sum _{z=0} ^{\min(H,W)} \left( {}_H \mathrm{C}_z {}_W \mathrm{C}_z z! 4^z \sum _{x=0} ^{\min(H-z,\left\lfloor \frac{W-z}{2} \right\rfloor)} \sum _{y=0} ^{\min(W-z-2x,\left\lfloor \frac{H-z-x}{2} \right\rfloor)} {}_{H-z} \mathrm{C}_x \frac{(W-z)!}{2^x (W-z-2x)!} {}_{W-z-2x} \mathrm{C}_y \frac{(H-z-x)!}{2^y (H-z-x-2y)!} \right) - 1 \end{aligned}\) です。愚直に求めると \(O(HW \min(H,W))\) かかりますが、これを高速化します。右側のΣの中を式変形します。

\(\begin{aligned} {}_{H-z} \mathrm{C}_x \frac{(W-z)!}{2^x (W-z-2x)!} {}_{W-z-2x} \mathrm{C}_y \frac{(H-z-x)!}{2^y (H-z-x-2y)!} &= \frac{(H-z)!}{(H-z-x)!x!} \times \frac{(W-z)!}{2^x (W-z-2x)!} \times \frac{(W-z-2x)!}{(W-z-2x-y)!y!} \times \frac{(H-z-x)!}{2^y (H-z-x-2y)!} \\ &= (H-z)! (W-z)! \times \frac{1}{2^{x+y} x! y! (W-z-2x-y)! (H-z-x-2y)!} \end{aligned}\)

\(l=x+y\) とすると、

\(\begin{aligned} \frac{1}{2^{x+y} x! y! (W-z-2x-y)! (H-z-x-2y)!} &= \frac{1}{2^l x!y! (W-z-l-x)! (H-z-l-y)!} \end{aligned}\)

\(A=W-z-l, B=H-z-l\) とすると、

\(\begin{aligned} \frac{1}{2^l x!y! (W-z-l-x)! (H-z-l-y)!} &= \frac{{}_A \mathrm{C}_x {}_B \mathrm{C}_y}{2^l A! B!} \end{aligned}\)

となります。有効な \(x,y\) についてこれを足すと \(\displaystyle \frac{{}_{A+B} \mathrm{C}_l}{2^l A!B!}\) となるので、各 \(x,y\) に対して答えを求めるところを各 \(l\) について求めると、計算量は \(O(HW \log mod)\) になります。

実装例 (C++) : https://atcoder.jp/contests/joisc2018/submissions/78328087