No.046 D

あるマスを左に移動すると仮定すると, その下のマスには左からしか入れなくなるので, あるマスの左下のマスも左に移動するしかない. 下に移動すると仮定しても同様に左下のマスが確定する.

一番左上のマスを仮定してそこから右下を確定させていき, 再度一番左上に戻るのは $uH = vW$ となるときであり, これは $H, W$ の最小公倍数である. よって, $g = \gcd(H, W)$ と置くと, $HW/g$ 個左下を確定させれば左上に戻る.

このことから, 仮定する数は $HW/(HW/g) = g$ 個である.

左上から最初の $g$ 歩を仮定すると, その移動先は左上のマスの仮定によって確定したマスであるので, あとは最初の $g$ 歩と同じ動きを繰り返すことになる.

最初の $g$ 歩の移動を $HW/g$ 回繰り返したときに初めて左上に戻る場合にのみ, すべてのマスを塗れる.

ここで, 最初の $g$ 歩の移動先を $(y, x)$ とする. 当然ながら, $y+x = g$ である. この移動を何回繰り返せば初めて左上に戻るかを考える. その回数を $n$ とすると, $yn = sH, xn = tW$ となり, $g_y = \gcd(y, H), g_x = \gcd(x, W)$ とおくと, $n$ は $H/g_y$ と $W/g_x$ の最小公倍数となる.

これが $HW/g$ に一致していれば, 最初の $g$ 歩で $(y, x)$ に移動したときにすべてのマスを塗れる. なお, 最初の $g$ 歩で $(y, x)$ に移動する組み合わせの数は ${}_gC_y$ である. (階乗と逆元はあらかじめ計算しておく)

これをすべての $(y, x)$ について (高々 $g+1$ 通り) 試し, すべてのマスが塗れる場合の組み合わせの数を足し合わせたものが答えとなる.