No.065 C

$N \geq M$ と仮定しても一般性を失わない.

$N-M \gt 1$ のとき

隣り合う犬が必ず現れるので $0$ 通りである.

$N-M = 0$ のとき

犬猿犬猿の順に並べるとき, 犬および猿を並べる順序はそれぞれ $N!, M!$ 通りなので $N!M!$ 通りである.

猿犬猿犬の順に並べるときも同じパターン数があるので, 答えは $2N!M!$ 通りである.

$N-M = 1$ のとき

犬猿犬猿の順に並べるしかない. よって $N!M!$ 通りである.