No.93

$x \times x$ の盤面の最下段のどこかの列に飛馬を置いたときの組み合わせの数を DP で更新する.

隣り合う列に置いてある飛馬の行の差が2のときを異常列対とする.

状態としては, $x$, 異常列対の数, $x-1$ 行目と $x-3$ 行目で異常列対があるか, $x-2$ 行目と $x$ 行目で異常列対があるか, を取り値としては組み合わせの数を取る.

$x+1$ 行目のどの列に置くかによって, 異常列対の数が以下のように変化する.

• $x-1$ 行目と $x-3$ 行目に異常列対がある場合, その間に置くと $x-1$ 行目と $x-3$ 行目の異常列対は解消されるが, 新たに $x+1$ 行目と $x-1$ 行目の異常列対が発生するので, 異常列対の数は変わらない.

• それ以外の異常列対の間に置くと, 異常列対が1つ減る.

• $x-1$ 行目に置いてある列の両隣に置くと異常列対が1つ増える. ただし, $x-1$ 行目と $x-3$ 行目に異常列対がある場合は片隣だけ.

• それ以外の場合は異常列対は変化しない.